Qualitative relativizations of complexity classes

DOI10.1016/0022-0000(85)90053-4MaRDI QIDQ1061119zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Quantitative Relativizations of Complexity Classes
• Positive Relativizations of Complexity Classes
• Positive relativizations of the \(P=?\) NP problem
• scientific article; zbMATH DE number 4011940
• scientific article; zbMATH DE number 4172379

Cites work

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

Cited in

(27)

• Dimension Characterizations of Complexity Classes
• scientific article; zbMATH DE number 1453080 (Why is no real title available?)
• Robust machines accept easy sets
• Complexity classes as mathematical axioms. II
• SELF-SPECIFYING MACHINES
• Strong and robustly strong polynomial-time reducibilities to sparse sets
• A comparison of polynomial time completeness notions
• Characterizing polynomial complexity classes by reducibilities
• On Tally Relativizations of $BP$-Complexity Classes
• Exotic quantifiers, complexity classes, and complete problems
• scientific article; zbMATH DE number 4114605 (Why is no real title available?)
• Positive relativizations for log space computability
• Collapsing degrees via strong computation
• scientific article; zbMATH DE number 4172379 (Why is no real title available?)
• The strong exponential hierarchy collapses
• ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES
• On relativizations with restricted number of accesses to the oracle set
• Quantitative Relativizations of Complexity Classes
• Reducing the number of solutions of NP functions
• Weighted automata and logics meet computational complexity
• On the Relations Between Discrete and Continuous Complexity Theory
• scientific article; zbMATH DE number 4077187 (Why is no real title available?)
• RelativizedNC
• Capturing Relativized Complexity Classes without Order
• Decomposing the complexity quotient category
• Optimal advice
• Cluster computing and the power of edge recognition

This page was built for publication: Qualitative relativizations of complexity classes

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