This lesson's interactive features are locked, please to keep using them
NP-Hard
All NP-complete problems are NP-hard, but not all NP-hard problems are NP-complete. The determining factor between NP-complete and NP-hard is that not all NP-hard problems are in NP.
Definition
A problem is
NP-hardif every problem inNPcan be reduced into it in polynomial time.
Compare this to the slightly different definition of NP-complete:
A problem is
NP-completeif it is inNPand every other problem inNPcan be reduced into it in polynomial time.
The difference is that NP-complete problems must be in NP, or in other words, they must be verifiable in polynomial time. NP-hard has no such restriction.