In 1975, Baker, Gill, and Solovay showed that there are oracles A, B so that P^A neq NP^A and P^B = NP^B. This shows that relativizing techniques won't settle the question of whether P = NP. However, some have interpreted this result to show that diagonalization won't settle the P = NP question since the diagonalization techniques that we are familiar with seem to relativize. However, in 1980, Kozen proved a result which he interpreted as saying that "if P neq NP is provable at all, then it is provable by diagonalization." One difficulty with this interpretation is that there is no generally-accepted definition of "separation by diagonalization." Regarding Kozen's result, Fortnow wrote in 2000 paper that "I believe (Kozen's) result says more about the difficulty of exactly formalizing the notion of a `diagonalization proof' than of actually arguing the diagonalization technique is the only technique we have for class separation."

In this talk, we will discuss some recent work of Impagliazzo, Nash and Remmel on the power of diagonalization. In particular, we will define two notions of diagonalization, strong diagonalization and weak diagonalization (which is implicit in Kozen's result). In contrast to Kozen's result that virtually every separation can be recast as weak diagonalization, we show that there are classes of languages which cannot be separated by strong diagonalization and provide evidence that strong diagonalization does not relativize. We also define two kinds of indirect diagonalization and discuss their power.

For further information please see the Logic and Computation Seminar web page.