Proof that the halting problem is NP
(I apologize if this is the wrong site for this question, but given that there are many "not-hard-enough-for-CS-Theory" CS theory questions floating around here, I think that this might be a good fit. Please feel free to move this if it's inappropriate.)
In this answer to a question about the definitions of NP, NP-hard, and NP-complete, Jason makes the claim that
The halting problem is the classic NP-hard problem. This is the problem that given a program P and input I, will it halt? This is a decision problem but it is not in NP. It is clear that any NP-complete problem can be reduced to this one.
While I agree that the halting problem is intuitively a much "harder" problem than anything in NP, I honestly cannot come up with a formal, mathematical proof that the halting problem is NP-hard. In particular, I cannot seem to find a polynomial-time many-to-one mapping from instances of every problem in NP (or at least, any known NP-complete problem) onto the halting problem.
Is there a straightforward proof that the halting problem is NP-hard?
We begin by noting that all NP-complete problems are reducible to 3SAT. Now we have a Turing machine that iterates over all possible assignments, and if a satisfying assignment is not found then it runs forever. This machine halts if and only if the 3SAT instance is satisfiable.
Completing the proof - we can, in polynomial time, reduce any instance of an NP-complete problem to 3SAT. From there, we can reduce this problem to an instance of the halting problem by pairing the input with a description of the Turing machine described above (which has constant size). This pairing can be done in polynomial time, because the Turing machine has only constant size. Then, the original NP-complete problem has answer "yes" iff 3SAT instance is satisfiable iff the Turing machine halts on the given input.
链接地址: http://www.djcxy.com/p/39982.html上一篇: 不同的子序列在数组中求和给定的数字
下一篇: 证明暂停问题是NP