A set is autoreducible if it can be reduced to itself by a Turing machine t
hat does not ask its own input to the oracle. We use autoreducibility to se
parate the polynomial-time hierarchy from exponential space by showing that
all Turing complete sets for certain levels of the exponential-time hierar
chy 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 diagonalizatio
n, our proofs separate classes solely by showing they have different struct
ural 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 fo
r doubly exponential time are autoreducible, we would separate either polyn
omial time from polynomial space, and nondeterministic logarithmic space fr
om nondeterministic polynomial time, or else the polynomial-time hierarchy
from exponential time.
We also look at the autoreducibility of complete sets under nonadaptive, bo
unded query, probabilistic, and nonuniform reductions. We show how settling
some of these autoreducibility questions will also lead to new complexity
class separations.