391. What is the difference between NP-complete and NP-hard?
MediumComplexity classes
Technical
Show model answer
A problem X is NP-hard if every problem in NP reduces to X in polynomial time, so a polynomial algorithm for X would give one for all of NP. X is NP-complete if it is NP-hard and also in NP. So NP-complete problems are the hardest problems inside NP.
NP-hard problems need not be in NP or even be decision problems: the optimisation version of TSP is NP-hard, and the halting problem is NP-hard but undecidable. To prove a new problem NP-complete, show it is in NP (give a verifier) and reduce a known NP-complete problem to it, in that direction.
What interviewers listen for
- NP-complete = NP-hard ∩ NP
- Reduce from a known hard problem to the new one