Relativization: a Revisionistic Retrospective

• Authors: J. Hartmanis, R. Chang, S. Chari, D. Ranjan and P. Rohatgi.
• Cite as: In Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, editors, pp. 537-547, World Scientific, 1993.
• Previous incarnations:
  • In Bulletin of the European Association for Theoretical Computer Science, 47:144-153, June 1992.
• Most readable version: book version.
• Status: complete.
• Online: book version available as a PDF file (with embedded Type 1 fonts): rev-book.pdf.

Abstract:

In this column we examine the role of relativization in complexity theory in light of recent non-relativizing results involving interactive protocols. We begin with the twice-told tale of the relativization principle and ponder upon its possible demise. Then, we discuss whether usual assumptions are historically accurate.