The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.5 / (2000))
Separating Complexity Classes Using Autoreducibility
Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet,
Pages. 1497-1520
Abstract A set is autoreducible if it can be reduced to itself by a Turing
machine that does not ask its own input to the oracle. We use
autoreducibility to separate the polynomial-time hierarchy from
exponential space by showing that all Turing complete sets for
certain levels of the exponential-time hierarchy are autoreducible
but there exists some Turing complete set for doubly exponential
space that is not. \ Although we already knew how to separate
these classes using diagonalization, our proofs separate classes
solely by showing they have different structural properties, thus
applying Post's program to complexity theory. We feel such
techniques may prove unknown separations in the future. In
particular, if we could settle the question as to whether all
Turing complete sets for doubly exponential time are
autoreducible, we would separate either polynomial time from
polynomial space, and nondeterministic logarithmic space from
nondeterministic polynomial time, or else the polynomial-time
hierarchy from exponential time. \ We also look at the
autoreducibility of complete sets under nonadaptive, bounded
query, probabilistic, and nonuniform reductions. We show how
settling some of these autoreducibility questions will also lead
to new complexity class separations.
Contents 1. Introduction 2. Notation and preliminaries 3. Nonautoreducibility results 4. Autoreducibility results 5. Separation results 6. Conclusion
Key words complexity classes, completeness, autoreducibility, coherence
Mathmatical Subject Classification 68Q15, 68Q05, 03D15