NP-Complete VS NP-Hard
I am trying to understand the difference between NP-Complete and NP-Hard.
Below is my understanding
An NP-Hard problem is one that is not solvable in polynomial time but can be verified in polynomial time.
An NP-Complete problem is one that is in NP and is also NP-Hard.
Is the above definition correct? If so, What about problems not In NP but NP-Hard. Wouldn't they be harder than NP-Complete problem, say they can only be solved and verified in exponential time?
Answer
A NP problem (not NP-Hard problem) is a decision problem which can be verified in polynomial time. Maybe they are solvable in polynomial time, since all problems in P are also in NP.
A NP-complete problem is a decision problem, which all NP problems can reduced to in polynomial time. They are the hardest problems in the class NP.
The NP-hard class is the class of the problems which are at least as hard as the NP-complete problem. They are not necessarily a decision problem. Given that we don't know whether NP = P or not, it would be hard to say whether we can verify a NP-hard problem in polynomial time.
For example, the decision problem of maximum clique (Give a graph G an integer K, to tell whether there is a complete graph with at least K vertices ) is NP problem. It is also NP-complete and NP-hard. However, maximum clique problem (Find the maximum clique in the given Graph) is not NP or NP-complete, since it is not decision problem. We can say it is NP-hard, since it is at least as hard as the decision version of maximum clique problem.