NP-Hard vs NP-Complete

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.

By Arun

Leave a Reply

Your email address will not be published. Required fields are marked *