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

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?

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