NP-hard problems that are not NP-complete are harder?

computer-science complexity-theory p-np
Nicky picture Nicky · Sep 28, 2010 · Viewed 21.6k times · Source

From my understanding, all NP-complete problems are NP-hard but some NP-hard problems are known not to be NP-complete, and NP-hard problems are at least as hard as NP-complete problems.

Is that mean NP-hard problems that are not NP-complete are harder? And how it is harder?

Answer

Sushant Sharma picture Sushant Sharma · Jun 18, 2011

To answer this question, you first need to understand which NP-hard problems are also NP-complete. If an NP-hard problem belongs to set NP, then it is NP-complete. To belong to set NP, a problem needs to be

(i) a decision problem,
(ii) the number of solutions to the problem should be finite and each solution should be of polynomial length, and
(iii) given a polynomial length solution, we should be able to say whether the answer to the problem is yes/no

Now, it is easy to see that there could be many NP-hard problems that do not belong to set NP and are harder to solve. As an intuitive example, the optimization-version of traveling salesman where we need to find an actual schedule is harder than the decision-version of traveling salesman where we just need to determine whether a schedule with length <= k exists or not.

Related questions

What's "P=NP?", and why is it such a famous question?

The question of whether P=NP is perhaps the most famous in all of Computer Science. What does it mean? And why is it so interesting? Oh, and for extra credit, please post a proof of the statement's truth or …

Read More
Explain the proof by Vinay Deolalikar that P != NP

Recently there has been a paper floating around by Vinay Deolalikar at HP Labs which claims to have proved that P != NP. Could someone explain how this proof works for us less mathematically inclined people?

Read More
What is a plain English explanation of "Big O" notation?

I'd prefer as little formal definition as possible and simple mathematics.

Read More