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.
• Online: submission to Bulletin available as a PDF file (with embedded Type 1 fonts): contra.pdf.

Abstract:

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.