- Authors: H. Buhrman, L. Fortnow, D. van Melkebeek, and L. Torenvliet.

- Reference:
*SIAM Journal on Computing*, 29(5): 1497-1520, 2000.

#### 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.