Using Autoreducibility to Separate Complexity Classes

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 (E. Pos, 1944) 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.

Authors

• Harry Buhrman
• Lance Fortnow
• Leen Torenvliet

Keywords

• Polynomials
• Turing machines
• Computer science
• TV
• Contracts
• Noise measurement
• Complexity theory
• Complex Class
• Class Separation
• Exponential Time
• Turing Machine
• Proof Of Theorem
• Computational Theory