Menu
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?
570
There are decision problems that are NP-hard but not NP-complete such as the halting problem. That is the problem which asks "given a program and its input, will it run forever?" That is a yes/no question and so is a decision problem. It is easy to prove that the halting problem is NP-hard but not NP-complete.
NP-hard problems are equally hard or harder than NP problems. This implies that they can be more complex and don't need to be a part of the set of NP problems at all. The problems in computer science can be termed as NP-hard if there is an NP-complete problem that can be reduced to that problem in any polynomial time.
NP Hard VS NP Complete Problem. NP-Hard problems (say X) can be solved if and only if there is a NP-Complete problem (say Y) can be reducible into X in polynomial time. NP-Complete problems can be solved by deterministic algorithm in polynomial time. To solve this problem, it must be a NP problem.
"Each instance of an NP-complete problem is difficult." Often some instances, or even most instances, may be easy to solve within polynomial time. However, unless P=NP, any polynomial-time algorithm must asymptotically be wrong on more than polynomially many of the exponentially many inputs of a certain size.
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.
55
Turing machine halting problem is undecidable on Turing machines and NP-hard, but not NPC. Apparently it is harder ;)
37
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
