Show that Halting problem $(\mathsf{HP\text{}})$ is $\mathsf{NP\text{-}Hard}$

Question

Let me define first Halting problem $(\mathsf{HP\text{}})$.

Given : $(M , x)$, $M$ is a turing machine and $x$ is a input binary string to turing machine $M$.

Decide : Does $M$ halt on string $x$?

I tried to reduce $\mathsf{SAT\text{}}$ instance to $\mathsf{HP\text{}}$ in polynomial time. Let $\phi$ be a instance of $\mathsf{SAT\text{}}$ and define a map $\mathsf{T\text{}} \colon \mathbb \phi \to\mathbb M$. If $\phi$ is satisfiable (means true) then turing machine $M$ will halt on string $x$ and if $\phi$ is not satisfiable (means false) then turing machine $M$ will not halt on string $x$.

I don't know whether the map $\mathsf{T\text{}}$ right or wrong. So my question is how to define a map and to compute this map in polynomial time?

Answer 1

Given a SAT formula $\varphi$, construct a Turing machine which iterates over all truth assignments for $\varphi$, and so determines if $\varphi$ is satisfiable or not. If it is, it halts. If it isn't, it doesn't halt (gets into an infinite loop).

As is apparent, in the same way we can show that the halting problem is coNP-hard (by reversing the decision rule at the end). Indeed, in the very same way we can show that the halting problem is hard for many other classes – in fact, for all classes defined by time or space constraints (deterministic, non-deterministic or randomized).

NP is the "length- and time-bounded" version of the halting problem, or rather, of $\Sigma_1$. The class $\Sigma_1$ consists of all predicates $P$ such that $$ P(x) \leftrightarrow \exists y \, \Pi(x,y), $$ where $\Pi$ is a computable predicate. NP is defined in a very similar way, by adding two restrictions:

1. $y$ has to be polynomially bounded (in $x$).
2. $\Pi$ has to be computable in polynomial time.

If you like this sort of thing, there is an entire field dedicated to this point of view, called Bounded Arithmetic.