hard problems that are not NP
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?
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.
Turing machine halting problem is undecidable on Turing machines and NP-hard, but not NPC. Apparently it is harder ;)
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.
链接地址: http://www.djcxy.com/p/6800.html上一篇: 完成计算机科学？
下一篇: 不是NP的难题