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.
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.
29 Oct 2007 22:31:05 EDT