Finally!

After a hiatus of almost four year, the graduate computational complexity course returns to Berkeley.

To get started, I proved Cook's non-deterministic hierarchy theorem, a 1970s result with a beautifully clever proof, which I first learned from Sanjeev Arora. (And that is not very well known.)

Though the full result is more general, say we want to prove that there is a language in NP that cannot be solved by non-deterministic Turing machines in time $o(n^3)$.

(If one does not want to talk about non-deterministic Turing machines, the same proof will apply to other quantitative restrictions on NP, such as bounding the length of the witness and the running time of the verification.)

In the deterministic case, where we want to find a language in P not solvable in time $o(n^3)$, it's very simple. We define the language $L$ that contains all pairs $(\langle T\rangle,x)$ where: (i) $T$ is a Turing machine, (ii) $x$ is a binary string, (iii) $T$ rejects the input $(\langle T\rangle,x)$ within $|(\langle T\rangle,x)|^3$ steps, where $|z|$ denotes the length of a string $z$.

It's easy to see that $L$ is in P, and it is also easy to see that if a machine $M$ could decide this problem in time $\leq n^3$ on all sufficiently large inputs, then the behavior of $M$ on input $\langle M\rangle,x$, for every $x$ long enough, leads to a contradiction.

We could try the same with NP, and define $L$ to contain pairs $(\langle T\rangle,x)$ such that $T$ is a non-deterministic Turing machine that has no accepting path of length $\leq |\langle T\rangle,x|^3$ on input $(\langle T\rangle,x)$. It would be easy to see that $L$ cannot be solved non-deterministically in time $o(n^3)$, but it's hopeless to prove that $L$ is in NP, because in order to solve $L$ we need to decide whether a given non-deterministic Turing machine rejects, which is, in general, a coNP-complete problem.

Here is Cook's argument. Define the function $f(k)$ as follows: $f(1):=2$, $f(k):= 2^{(1+f(k-1))^3}$. Hence, $f(k)$ is a tower of exponentials of height $k$. Now define the language $L$ as follows.

$L$ contains all pairs $\langleT \rangle,0^t$ where $\langle T\rangle$ is a non-deterministic Turing machine and $0^t$ is a sequence of $t$ zeroes such that one of the following conditions is satisfied

1. There is a $k$ such that $f(k)=t$, and $T$ has no accepting computation on input $\langle T\rangle,0^{1+f(k-1)}$ of running time $\leq (1+(f(k-1))^3$;
   
2. $t$ is not of the form $f(k)$ for any $k$, and $T$ has an accepting computation on input $\langle T\rangle,0^{1+t}$ of running time $\leq (t+1)^3$.
   

Now let's see that $L$ is in NP. When we are given an input $\langle T\rangle,0^t$ we can first check if there is a $k$ such that $f(k)=t$.

1. If there is, we can compute $t':=f(k-1)$ and deterministically simulate all computations of $T$ on inputs $\langle T\rangle,0^{t'}$ up to running time $t'^3$. This takes time $2^{O(t'^3)}$ which is polynomial in $t$.
   
2. Otherwise, we non-deterministically simulate $T$ on input $\langle T\rangle,0^{t+1}$ for up to $(t+1)^3$ steps. (And reject after time-out.)
   

In either case, we are correctly deciding the language.

Finally, suppose that $L$ could be decided by a non-deterministic Turing machine $M$ running in time $o(n^3)$. In particular, for all sufficiently large $t$, the machine runs in time $\leq t^3$ on input $\langle M\rangle,0^t$.

Choose $k$ to be sufficiently large so that for every $t$ in the interval $1+f(k-1),...,f(k)$ the above property is true.

Now we can see that $M$ accepts $(\langle M\rangle,0^{f(k-1)+1})$ if and only if $M$ accepts $(\langle M\rangle,0^{f(k-1)+2})$ if and only if ... if and only if $M$ accepts $(\langle M\rangle,0^{f(k)})$ if and only if $M$ rejects $(\langle M\rangle,0^{f(k-1)+1})$, and we have our contradiction.