Thank you. you are right. Finding a Hamiltonian cycle in a graph is NP Hard.
The difference is, that an NP-hard problem needs not to be in the class NP, while any NP-complete problem is by definition also NP-hard. The "HALTING problem" is NP-hard, but not NP-complete.
A decision problem A∈NP is NP-complete if all other problems of class NP are reduced polynomially to the problem A. if a polynomial deterministic algorithm exists to solve an NP-complete problem then all problems of class NP may be solved in polynomial time. NP-hard problems are optimization problems whose associated decision problems are NP-Complete. Most of the real world optimization problems are NP-Hard for which efficient algorithm do not exist. look at "meta heuristics from design to implementation , EL-Ghazalitalbi") for more information
For an intuitive explanation see (Google is your friend):
http://stackoverflow.com/questions/1857244/np-vs-np-complete-vs-np-hard-what-does-it-all-mean
Essentially an NP-complete problem is an NP problem to which all other NP problems can be reduced in polynomial time, so that if one could find an efficient (P) solution to it, all NP problems could be solved in polynomial time in the same way.
For NP-hard a more detailed description is here:
http://en.wikipedia.org/wiki/NP-hard
Essentially NP-hard is any problem which is harder than all NP problems, so that they could be solved in polynomial time by relying on solutions to the NP-hard problem. I like the view in terms of Oracles (as it is in wikipedia too), but you need to know what an Oracle is. This, by the way contradicts what Atalay Ileri says above, as the halting problem (though not decidable) is indeed NP-hard (as Marc Hellmuth stated), although is not even decidable. In any case this is a somehow strange/exotic example of NP-hard.
Either way, do not expect to get to understand this subtleties without studying some computation theory: Turing Machines, etc. The question of complexity classes requires some deep understanding of computation theory and is not always intuitive.
A language L is NP-hard if for every L' in NP, L is at least as hard as L'. A language L is NP-complete if 1) L belongs to NP and 2) L is NP-hard.
By Cook's Theorem SAT is NP-complete. The problems MAX-SAT, MAX-CL, MAX-CUT and MIN-VC are NP-hard.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics