mjhjmtu

I was going through the lecture of prof. Erik Demaine and he said that a problem X is NP-Hard if it is at-least as hard as every problem Y that belongs to NP class.

He further said that if we can prove that there exists a problem that belongs to NP but not to P, then we can absolutely be sure that NP hard problems don't belong to P class.

Here is my question... What happens if P=NP. Thus it mean that all NP-hard problems become polynomially solvable? Will all NP hard problems reduce to polynomial order if P=NP?

No. A problem is Np-Hard if all NP problems are reducible to an instance of that problem in polynomial time. Some NP-Hard problems cannot be solved in nondeterministic polynomial time, and are not in NP. Then these problems will not be polynomial time solvable regardless of whether or not P=NP.

The halting problem is NP-hard: given any language $L$ in P accepted by some nondeterministic machine $M$, we can come up with a polytime reduction that on input $x$ constructs a Turing machine which runs $M$ on $x$ and all possible witnesses, halting if $M$ accepts any of them, and going into an infinite loop otherwise.

We know unconditionally that the halting problem is not computable, and so in particular, isn’t in P.

So just as your Prof. wikipedia says (emphasis mine):

NP-hardness [...]is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP"

(Still Informally) you can think of the ‚at least‘ as:

NP $leq$ NP-Hard

So you have to distinguish those NP-hard problems for which the equality holds from those which are ,strictly‘ harder. I.e problems that are NP-hard and are also in NP (a.k.a NP-complete) vs problems which are NP-hard but not in NP.

Looking at it this way, it should be realtively easy to reason about your question. Namely, if P=NP:

• For problems that are NP-hard and are also in NP it will obviously mean they are also in P (since P=NP by assumption)


• For problems that are NP-hard but not in NP it will mean nothing.

This euler diagram from wikipedia might also help to clear things up