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 .
(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 , it’s very simple. We define the language that contains all pairs where: (i) is a Turing machine, (ii) is a binary string, (iii) rejects the input within steps, where denotes the length of a string .
It’s easy to see that is in P, and it is also easy to see that if a machine could decide this problem in time on all sufficiently large inputs, then the behavior of on input , for every long enough, leads to a contradiction.
We could try the same with NP, and define to contain pairs such that is a non-deterministic Turing machine that has no accepting path of length on input . It would be easy to see that cannot be solved non-deterministically in time , but it’s hopeless to prove that is in NP, because in order to solve 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 as follows: , . Hence, is a tower of exponentials of height . Now define the language as follows.
contains all pairs where is a non-deterministic Turing machine and is a sequence of zeroes such that one of the following conditions is satisfied
- There is a such that , and has no accepting computation on input of running time ;
- is not of the form for any , and has an accepting computation on input of running time .
Now let’s see that is in NP. When we are given an input we can first check if there is a such that .
- If there is, we can compute and deterministically simulate all computations of on inputs up to running time . This takes time which is polynomial in .
- Otherwise, we non-deterministically simulate on input for up to steps. (And reject after time-out.)
In either case, we are correctly deciding the language.
Finally, suppose that could be decided by a non-deterministic Turing machine running in time . In particular, for all sufficiently large , the machine runs in time on input .
Choose to be sufficiently large so that for every in the interval the above property is true.
Now we can see that accepts if and only if accepts if and only if … if and only if accepts if and only if rejects , and we have our contradiction.