Separating Complexity Classes Using Autoreducibility

DOI10.1137/S0097539798334736MaRDI QIDQ4943880zbMATH OpenFDO

Authors Harry Buhrman, Dieter Van Melkebeek, Leen Torenvliet, Lance Fortnow

Publication date 19 March 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9807185

zbMATH Keywords

autoreducibilitycoherencecompletenesscomplexity classes

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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 polynomial 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 read to new complexity class separations.

Recommendations

• scientific article; zbMATH DE number 4077187
• Some Observations on Separating Complexity Classes
• Separation of deterministic, nondeterministic and alternating complexity classes
• scientific article; zbMATH DE number 4114605
• scientific article; zbMATH DE number 4120160
• Classifying the computational complexity of problems
• scientific article; zbMATH DE number 4074483
• scientific article; zbMATH DE number 3885883
• scientific article; zbMATH DE number 4108743
• The recursion-theoretic structure of complexity classes

Cited in

(17)

• Randomness and completeness in computational complexity
• Autoreducibility of NP-complete sets under strong hypotheses
• Non-uniform reductions
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• Introduction to autoreducibility and mitoticity
• A Post's program for complexity theory.
• Infinitely‐Often Autoreducible Sets
• scientific article; zbMATH DE number 4077187 (Why is no real title available?)
• Fine separation of average time complexity classes
• Autoreducibility of NP-complete sets
• Structural properties of nonautoreducible sets
• Algorithms and Computation
• Mathematical Foundations of Computer Science 2005
• Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
• Splitting NP-complete sets infinitely
• Autoreducibility, mitoticity, and immunity
• On the autoreducibility of functions

This page was built for publication: Separating Complexity Classes Using Autoreducibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4943880)