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

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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.