Qualitative relativizations of complexity classes

DOI10.1016/0022-0000(85)90053-4zbMath0569.03016OpenAlexW2081662755MaRDI QIDQ1061119

Timothy J. Long, Ronald V. Book, Selman, Alan L.

Publication date: 1985

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(85)90053-4

zbMATH Keywords

nondeterministic oracle Turing machine

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Related Items

Collapsing degrees via strong computation, A comparison of polynomial time completeness notions, Positive relativizations for log space computability, Cluster computing and the power of edge recognition, Characterizing polynomial complexity classes by reducibilities, RelativizedNC, On relativizations with restricted number of accesses to the oracle set, Robust machines accept easy sets, Strong and robustly strong polynomial-time reducibilities to sparse sets, ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES, Optimal advice, The strong exponential hierarchy collapses, SELF-SPECIFYING MACHINES, Reducing the number of solutions of NP functions

Cites Work

• Strong nondeterministic polynomial-time reducibilities
• Bounded query machines: on NP and PSPACE
• Bounded query machines: on NP( ) and NPQUERY( )
• A uniform approach to obtain diagonal sets in complexity classes
• Relative complexity of checking and evaluating
• Positive Relativizations of Complexity Classes
• Quantitative Relativizations of Complexity Classes
• Relativizations of Unambiguous and Random Polynomial Time Classes
• Relativized Questions Involving Probabilistic Algorithms
• On the Structure of Polynomial Time Reducibility
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question