Sign in
Oracles versus proof techniques that do not relativize
Book chapter   Peer reviewed

Oracles versus proof techniques that do not relativize

Algorithms, pp.39-52
Lecture Notes in Computer Science, Springer Berlin Heidelberg
06/04/2005

Abstract

Complexity Class Interactive Proof Complexity Theory Turing Machine Computation Tree
Oracle constructions have long been used to provide evidence that certain questions in complexity theory cannot be resolved using the usual techniques of simulation and diagonalization. However, the existence of nonrelativizing proof techniques seems to call this practice into question. This paper reviews the status of nonrelativizing proof techniques, and argues that many oracle constructions still yield valuable information about problems in complexity theory.

Metrics

15 Record Views

Details