Qualitative relativizations of complexity classes
A nondeterministic oracle Turing machine (TM) is strong if, relative to each oracle set, for each input x, there is at least one computation that either accepts x or rejects it and there are no contradictory computations. A TM is confluent if for each configuration I, all the computations branching out from I either lead to the same query configuration or do not lead to query configurations at all. A TM is mature if for every nonquery configuration I, if I leads either to an accepting computation or to a rejecting computation without reaching a query configuration, then the computations branching out from I do not contain any query configuration. The main result of this paper states that \(P=NP\cap co\)-Np if and only for every oracle D, \(P(D)=NP_ R(D)\) where \(NP_ R(D)\) is the class of languages accepted by strong, confluent and mature TM's that run in polynomial time. These restrictions are qualitative ones in contrast with quantitative relativizations where the number of accesses to the oracle is restricted. The work also contains an interesting discussion relative to the possibility of weakening the conditions for a positive qualitative relativization of the \(P=?NP\cap co\)-NP problem (no positive quantitative relativization is known).
- 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 the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativizations of Unambiguous and Random Polynomial Time Classes
- Relativized Questions Involving Probabilistic Algorithms
- Strong nondeterministic polynomial-time reducibilities
- Exotic quantifiers, complexity classes, and complete problems
- A comparison of polynomial time completeness notions
- Strong and robustly strong polynomial-time reducibilities to sparse sets
- Reducing the number of solutions of NP functions
- Collapsing degrees via strong computation
- Complexity classes as mathematical axioms. II
- Positive relativizations for log space computability
- Cluster computing and the power of edge recognition
- scientific article; zbMATH DE number 4172379 (Why is no real title available?)
- Characterizing polynomial complexity classes by reducibilities
- Quantitative Relativizations of Complexity Classes
- RelativizedNC
- On relativizations with restricted number of accesses to the oracle set
- scientific article; zbMATH DE number 4077187 (Why is no real title available?)
- On Tally Relativizations of $BP$-Complexity Classes
- Decomposing the complexity quotient category
- Capturing Relativized Complexity Classes without Order
- scientific article; zbMATH DE number 4114605 (Why is no real title available?)
- On the Relations Between Discrete and Continuous Complexity Theory
- scientific article; zbMATH DE number 1453080 (Why is no real title available?)
- SELF-SPECIFYING MACHINES
- ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES
- Dimension Characterizations of Complexity Classes
- The strong exponential hierarchy collapses
- Weighted automata and logics meet computational complexity
- Optimal advice
- Symmetric exponential time requires near-maximum circuit size
- Logical characterizations of weighted complexity classes
- Descriptive complexity and weighted Turing machines
- Robust machines accept easy sets
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)
