Diagonalization refers to a method of proving that some enumeration of an infinite set misses at least one element.
Perhaps the best way to introduce the idea is in a context other than complexity theory. Georg Cantor famously applied diagonalization to show that the set of real numbers is strictly larger than the set of integers, despite that they are both infinite. We shall show here a seemingly weaker version, where we show that , but it is easy to show that the integers and natural numbers have the same cardinality.
This is the most clean and intuitive example of how diagonalization arguments go, and shows the general pattern by which the method works. If we want to show that an enumeration is incomplete, then we construct a new element that is different from every single other item in that enumeration by construction. Though we have given a very specific example here, the argument generalizes to show that the cardinality of a set is always strictly less than that of its power set (see this article on MathWorld for more details).
Many very important proofs in complexity theory work by diagonalization arguments, including:
- Ladner's Theorem.
- The Time Hierarchy Theorem.
Limits of Diagonalization
There are limits to the power of diagonalization, however. To see this, we need to take a brief detour into oracle land. We define an oracle Turing machine (OTM) for some problem to be a Turing machine which has a special tape, called the oracle tape, and three special states . Whenever an OTM enters the special state , in the next step its new state shall be either or , depending on whether the contents of satisfy . Given the set of Turing machines in a class , we write that the class is the set of oracle Turing machines, where the oracle is for the problem . Thus, P3SAT is the set of polynomial-time deterministic Turing machines with oracles for 3SAT.
Diagonalization arguments treat TMs as black boxes, paying attention only to the fact that we can make an enumeration of machines and the ability to construct a new machine which simulates each machine in an enumeration with very little overhead. As such, we can substitute an oracle Turing machine for a Turing machine in any diagonalization argument. Since we can use this alternate model of computation in diagonalization arguments, any such argument which shows that also implies that for any , . We say that diagonalization arguments relativize.
As an example of how this fundamentally limits the power of diagonalization arguments, note that [BGS75] showed that there exist oracles such that P = NP and P ≠ NP. Thus no relativizing argument cannot prove either P = NP or P ≠ NP.