1
$\begingroup$

My notes on P vs NP say the following:

Every problem x in the NP-hard class has the following properties:
– There is no known polynomial-time algorithm for x.
– The only known algorithms take exponential time.
– If you could solve x in polynomial-time, then you could solve them all in polynomial-time.

The last point sounds like it's confusing NP-hard with NP-complete. I would appreciate it if someone would please clarify this.

$\endgroup$
1
$\begingroup$

The text is indeed incorrect for NP-hard problems and correct for NP-complete problems.

NP is the class of decision problems for which, given a problem instance and a candidate solution, the correctness of the solution can be verified with a polynomial-time algorithm. Another equivalent definition is that NP is the class of decision problems that can be solved in polynomial time by a Non-deterministic Turing Machine.

NP-hard problems are informally "decision problems at least as hard as the hardest problems in NP". A more rigorous definition is that a problem $P$ is NP-hard if every problem in NP can be reduced to $P$ in polynomial time: that is, knowing a polynomial-time algorithm for solving $P$ would allow us to solve any problem in NP in polynomial time by reduction to $P$. The text you provided suggests that this would extend to solving all problems in NP-hard in polynomial time, which is incorrect: notably NP-hard includes decision problems that are not solvable in the first place, such as the famous Halting problem. The text would be correct if it said "...then you could solve any problem in NP in polynomial time".

NP-complete problems are problems that are both NP and NP-hard: informally, they are the hardest problems of NP. Since they are in NP, it would indeed hold that solving one of them in polynomial time would imply the possibility of solving any of them in polynomial time.

$\endgroup$
1
$\begingroup$

The last part is wrong. Should be "If you could solve x in polynomial-time, then you could solve every NP-complete problem in polynomial-time"

And the difference between NP-complete and NP-hard is: If an instance of an NP-complete problem has the answer YES, then you can guess a proof that can be verified in polynomial time. That's not (necessarily) true for NP-hard problems.

All NP-complete problems are essentially equally hard (up to polynomial changes in size and execution time); NP-hard problems are not.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.