I was reading about Cook's Theorem for Turing machine. In its proof, it is said that the Turing machine would take at most $n^k$ steps (where $k$ is an integer and $k > 0$) to compute an input of length $n$.

This is probably assuming that the Turing machine does halt for the given input. It further says that we as there are at most $n^k$ steps, we don't need an infinite tape. A tape with $n^k$ elements is sufficient as the turning machine would not travel more than that.

Why do we say the Turing Machine needs at most $n^k$ steps?


Cook's Theorem is a theorem in the theory of computational complexity. Here, we are only interested in Turing machines whose time complexity is well-defined. This can only be the case for Turing machines that always halt.

Cook's Theorem states that the language

$$\mathrm{SAT} = \{ \langle \phi \rangle \mid \phi \; \text{is a satisfiable formula in propositional logic}\}$$

is NP-complete. To show this, we must show that for any language $L \in \mathrm{NP}$, $L$ polynomial-time reduces to $\mathrm{SAT}$.

But since $L \in \mathrm{NP}$, we know that there exists a nondeterministic Turing machine $M$ that decides $L$ and has polynomial time complexity. That is, we know there exists a $k > 0$ such that $M$ will never use more than $n^k$ steps for any input of size $k$. Within $n^k$ steps, $M$ can only visit $n^k$ cells on its tape.

| cite | improve this answer | |

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.