3
$\begingroup$

I'm quoting the following (landmark) paper:

Theodore Baker, John Gill, and Robert Solovay Relativizations of the P?=NP Question SIAM Journal of Computing, Volume 4, Number 4, December 1975, pages 431-442.

From the first page,"It seems unlikely that ordinary diagonalization are adequate for producing an example of a language in NP but not in P...".

I'm fairly rusty on math, so I was wondering if someone could briefly explain "ordinary" diagonalization and maybe give a few examples. I'd really like to see this in detail, beause I'd like to explore this more. Can they be as simple as I think they can be? I'm hoping to get a better understanding of the (possibly broad) grounds that diagonlization methods cover.

3 Answers 3

3

'Ordinary' diagonalization generally refers to Cantor's argument for showing the non-countability of the reals and similar schemes for generating counterexamples; enumerate all of the purported instances of some 'thing', then construct a new thing which differs by each of these instances at some value. For instance, strict inclusions in the time hierarchy such as DTIME($n$) $\subsetneq$ DTIME($n^2$) can be proven with this technique: consider an enumeration $M_x$ of Turing machines, and build a Turing machine $N$ which executes the following: 'On input $x$, run some canonically chosen UTM $U$ for $|x|^{1.5}$ steps to simulate the execution of $M_x$ on $x$; if $M_x$ outputs within this length of time then output $1-M_x(x)$, otherwise output $0$'. Then $N$ is trivially in DTIME($n^2$) (as it takes roughly $n^{1.5}$ steps for any input of length $n$), but since $N$ is $M_y$ for some $y$ (in fact, infinitely many $y$), if $N$ were in DTIME($n$) then we could use $U$ to simulate $N$ on its own code $y$ for $|y|^{1.5}$ steps, know that $N$ will have halted by that point (since it's in DTIME($n$)), and thus get that $N(y) = 1-N(y)$, contradiction.

8

Ordinary diagonalization relativizes. That means that if you prove some statement X regarding TMs using diagonalization, then statement X is also true if the TM model is extended by allowing it to use oracle queries.

It's not difficult to see that given an oracle for (say) PSPACE (i.e. an oracle for a PSPACE-complete problem), P=NP. Baker, Gill and Solovay constructed an oracle for which P$\neq$NP. So techniques that relativize can't solve the P vs. NP question.

A good example of diagonalization is the time-hierarchy and space-hierarchy theorems, which are generalizations of the method used to prove that the halting problem is undecidable. You can look them up on Wikipedia or in any introductory book on computational complexity.

4

Lance Fortnow has a nice survey of diagonalization in the Bulletin of the EATCS. In it, he gives examples of different kinds of "ordinary" diagonalization proofs, and also discusses the BGS result.