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. |
Post a Comment