-1

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?

Hans Hüttel
  • 4,271
Sukumar Gaonkar
  • 3

1 Answers1

0

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.

Hans Hüttel
  • 4,271