NP-hard |
NP-complete |
|---|
| NP-hard is the class of decision problems to which all problems in NP can be reduced to in polynomial time by a deterministic Turing machine. | NP-complete is the class of decision problems in NP to which all problems in NP can be reduced to in polynomial time by a deterministic Turing machine. |
| NP-hard ⊄ NP or NP ⊄ NP-hard. | NP-complete ⊂ NP. |
| Not all NP-hard problems are NP-complete. For an NP-hard problem to be NP-complete, it must be in NP. | All NP-complete problems are NP-hard |
| If any problem in NP can be reduced to it in polynomial time. | If any problem in NP can be reduced to it in polynomial time AND it is also in NP(and thus solutions can be verified in polynomial time). |
| These are the problems that are at least as hard as the NP-complete problems. Note that NP-hard problems do not have to be in NP, and they do not have to be decision problems. | NP-Complete is a complexity class which represents the set of all problems in NP for which it is possible to reduce any other NP problem in polynomial time. |
Arun Kumar