A language 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 exponential space from doubly exponential
space by showing that all Turing-complete sets for exponential space are
autoreducible but there exists some Turing-complete set for doubly
exponential space that is not. We immediately also get a separation of
logarithmic space from polynomial space.
Although we already know 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 complete sets for doubly exponential time were autoreducible
we would separate polynomial time from either logarithmic space or
polynomial space.
We also show several other theorems about autoreducibility.
(This is joint work with Harry Buhrman and Leen Torenvliet.)