31

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?

Nicky
  • 319
  • 1
  • 3
  • 3

6 Answers6

23

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.

Sushant Sharma
  • 447
  • 4
  • 8
10

Turing machine halting problem is undecidable on Turing machines and NP-hard, but not NPC. Apparently it is harder ;)

Chang Peng
  • 1,052
  • 8
  • 14
7

The set of NP-hard problems is a superset of the set of NP-complete problems. There are complexity classes more "difficult" than NP, for example PSPACE, EXPTIME or EXPSPACE, and all these contain NP-hard but not NP-complete problems.

Gintautas Miliauskas
  • 7,744
  • 4
  • 32
  • 34
6

Turing halting problem is undecidable and it belongs to NP-Hard set. For turing halting problem we do not have any decider as it is a RE language. So we do not have any algorithm to solve it. Thus it is clear that unsolvable problems are also in NP-Hard set . So NP-Hard set also contains the languages or problems for which we do not have any algorithm to solve.

Avijit Dutta
  • 61
  • 1
  • 1
2
  1. NP-complete must be NP and NP-hard.
  2. and NP-hard which are not NP-complete are not NP.
  3. Now by definition of NP there is someone who give answer instance for problem. and there is verifier to verify.
  4. this means NP-Hard does not have either one of them. Hence they are difficult to solve is True.
Toon Krijthe
  • 52,876
  • 38
  • 145
  • 202
user1778828
  • 21
  • 1
2

From http://en.wikipedia.org/wiki/NP-hard#Examples

There are also decision problems that are NP-hard but not NP-complete, for example the halting problem. This is the problem which asks "given a program and its input, will it run forever?" That's a yes/no question, so this is a decision problem. It is easy to prove that the halting problem is NP-hard but not NP-complete.

Sheldon L. Cooper
  • 3,230
  • 19
  • 13