Complexity Dojo/Diagonalization

Main Zoo - Complexity Garden - Zoo Glossary - Zoo References - Chris' Complexity Dojo

---

Major Theorems: Cook-Levin - Savitch's - Ladner's - Blum Speedup - Impagliazzo-Widgerson - Toda's - Natural Proofs

Proof Techniques: Diagonalization

Diagonalization refers to a method of proving that some enumeration $\{s_{1},s_{2},\dots \}$ of an infinite set misses at least one element.

Example

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 $\left\vert \mathbb {R} \right\vert >\left\vert \mathbb {N} \right\vert$, but it is easy to show that the integers and natural numbers have the same cardinality.

Theorem (Cantor's Diagonalization Argument). The set of real numbers $\mathbb {R}$ is strictly larger than the set of natural numbers $\mathbb {N}$. That is, there exists an injection (one-to-one function) $f:\mathbb {N} \to \mathbb {R}$, but that any such $f$ fails to be surjective (onto).

---

Proof: Showing that an injective function $f:\mathbb {N} \to \mathbb {R}$ exists is trivial; consider $f(n)=n$. On the other hand, suppose for the sake of contradiction that there exists some $f$ of the same form which is bijective (one-to-one and onto). Then, we can enumerate the real numbers: $\{f(1),f(2),f(3),\dots \}$. In particular, if we write out the decimal expansion of $f(i)$ as $f(i)=f_{i1}f_{i2}\dots$, where each $f_{ij}\in {0,1,2,3,4,5,6,7,8,9}$, then we can make a table as follows:

$f(1)$	=	$f_{11}$	$f_{12}$	$f_{13}$	$f_{14}$	$f_{15}$	$\cdots$
$f(2)$	=	$f_{21}$	$f_{22}$	$f_{23}$	$f_{24}$	$f_{25}$	$\cdots$
$f(3)$	=	$f_{31}$	$f_{32}$	$f_{33}$	$f_{34}$	$f_{35}$	$\cdots$
$f(4)$	=	$f_{41}$	$f_{42}$	$f_{43}$	$f_{44}$	$f_{45}$	$\cdots$
$f(5)$	=	$f_{51}$	$f_{52}$	$f_{53}$	$f_{54}$	$f_{55}$	$\cdots$

Now, consider $g=g_{1}g_{2}g_{3}\dots$, where each $g_{i}=f_{ii}+1{\bmod {1}}0$. For example, if $f_{22}=9$, then $g_{2}=0$. Intuitively, we construct $g$ by selecting digits from the diagonal of the table above, and shifting each by one. But then, we claim that for any $i\in \mathbb {N}$, $g\neq f(i)$. To see this, note that $f(i)$ and $g$ must differ in at least one digit–the $i^{\mathrm {th} }$ digit–by construction. (Note that there is a slight technicality that we're sweeping under the rug here: 0.999.... = 1.0000, but they differ in every digit. I say that this technicality is slight, however, as we could deal with this as a special case.)

Therefore, $g$ is not in our enumeration and so $f$ is not surjective. ▪

Applications

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 $O$ to be a Turing machine which has a special tape, called the oracle tape, and three special states $q_{?},q_{\mbox{yes}},q_{\mbox{no}}$. Whenever an OTM enters the special state $q_{?}$, in the next step its new state shall be either $q_{\mbox{yes}}$ or $q_{\mbox{no}}$, depending on whether the contents $w$ of satisfy $w\in O$. Given the set of Turing machines in a class $A$, we write that the class $A^{O}$ is the set of oracle Turing machines, where the oracle is for the problem $O$. Thus, P^3SAT 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 $A\neq B$ also implies that for any $O$, $A^{O}=B^{O}$. 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 $A,B$ such that P^$A$ = NP^$B$ and P^$B$ ≠ NP^$B$. Thus no relativizing argument cannot prove either P = NP or P ≠ NP.