3
$\begingroup$

I have just been reading through a SO post which proves that the Halting Problem is NP-Hard. Whilst this is an easily followed proof, one slight slight aspect of it has left me scratching my head: it says that

"This pairing can be done in polynomial time, because the Turing machine has only constant size."

So their justification for saying that the reduction was done in polynomial time is that the Turing machine 'only has constant size'.

Why would this prove that the reduction was done in polynomial time?

$\endgroup$
5
$\begingroup$

The reduction described in the mentioned post, from SAT to the halting problem, performs the following mapping:

$$\varphi\mapsto \big(\langle M\rangle,\varphi \big)$$

where $\varphi$ is a CNF formula and $M$ is the Turing machine which given a CNF $\psi$ as input, iterates over all the possible assignments to the variables of $\psi$, and enters a loop iff no satisfying assignment was found.

The machine $M$ does not depend on the input of the reduction, so it has some constant size description independent of the input $\varphi$. This means that you can output $\langle M \rangle$ in polynomial (even constant) time relative to the size of $\varphi$, hence the reduction is computable in polynomial time.

Note that you only need to show that you can generate $\langle M \rangle$ in polynomial time, which does not necessarily mean it has to have a constant size. Suppose e.g. that we want to show that $L=\{\langle M\rangle | \text{M halts on input $\epsilon$}\}$ is NP hard. In that case, the reduction $\varphi\mapsto \langle M_{\varphi}\rangle$ does the trick, where $M_{\varphi}$ is the machine which ignores its input, iterates over all possible assignments for $\varphi$, and enters a loop if no satisfying assignment was found. $M_{\varphi}$ does not have a constant size description, since you have to hardcode $\varphi$ into it. However, you can still generate $\langle M_{\varphi}\rangle$ in polynomial time, which makes the reduction polynomial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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