Proof that the halting problem is NP-hard?

问题:

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?

回答1:

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.