Proof that the halting problem is NP-hard? [closed]

Question

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?

Besot

Answer 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.

Fetching

Thanks so much! I was missing the intermediate step of introducing a TM that solves the problem. – Besot

The halting problem is well-known to be undecidable, so how can there be an algorithm that decides in in NP-complete time? – Hathaway

@Hathaway The halting problem is not NP-complete (because, as you note, it is not decidable thus not in NP), but it is NP-hard (that is, at least as hard as everything in NP after a polynomial-time reduction) because every decision problem can be reduced to it. – Matchbook

It is not clear to me how 3SAT can be reduced to HP in polynomial time, given that the iteration is exponential – Butterwort

@Butterwort Only the reduction itself - that is, the construction of the TM that iterates over all the assigments - has to run in polynomial time. Solving the problem you reduced to (i.e., letting the TM run) does not need to be polynomial. – Pathway

Well explained. I have a question, doesn't this explanation show that the decision version of SAT reduces to the halting problem? If yes, is that sufficient (Is the decision version of SAT NP-Complete)? – Acrid

@PraveshJain To show a problem is NP-Complete, you have to show it in in NP, and that you can reduce another NP-Hard problem to your problem. So in this case, you need to reduce some other NP-Hard problem to SAT (the opposite was done here). But yes, SAT is NP-Complete. – Sharecropper

"and if a satisfying assignment is not found then it runs forever", why is this true? – Yarndyed

@Yarndyed that is how you construct the machine. Suppose you're writing an algorithm, which checks every assignment and if no satisfying assignment is found, then you simply do "while True {};" – Heptagon

Good explanation, would have elaborated more on 3SAT in polynomial time. "while True {};" is very neat. @Heptagon – Duodiode