An Example of a Theorem that has Contradictory Relativizations
and a Diagonalization Proof


The central questions in complexity theory (e.g. the P =? NP question) can only be solved with proof techniques that do not relativize. There had been some debate about whether such techniques are within reach of the "current state of mathematics". Recent advances in the area of interactive protocols have produced techniques that do not relativize. However, these advances do not resolve the debate on whether diagonalization can be used to solve problems that have contradictory relativizations. This paper gives an example of a theorem that has contradictory relativizations and a diagonalization proof.

Last Modified: 29 Oct 2007 13:32:56 EDT by Richard Chang