An Example of a Theorem that has Contradictory Relativizations
and a Diagonalization Proof
- Authors: R. Chang.
- Cite as:
In Bulletin of the European Association for Theoretical
Computer Science, 42:172-173, October 1990.
- Previous incarnations:
- Technical Report 89-1059, Department of Computer Science,
Cornell University, November 1989.
- Most readable version: Bulletin version.
- Status: complete.
submission to Bulletin available as a PDF file (with
embedded Type 1 fonts): contra.pdf.
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
29 Oct 2007 13:32:56 EDT