Skip to interview prep
Apexed

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
What is the difference between NP-complete and NP-hard — Data structures & algorithms interview question — Apexed