Relativization: a Revisionistic Retrospective


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.

Last Modified: 29 Oct 2007 22:31:05 EDT by Richard Chang