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

coherencecomplexity classescompletenessautoreducibility

Mathematics Subject Classification ID

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

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)

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

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)