Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
From MaRDI portal
Publication:912625
DOI10.1007/BF02125350zbMath0698.68051MaRDI QIDQ912625
Publication date: 1989
Published in: Combinatorica (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (25)
Exact lower time bounds for computing Boolean functions on CREW PRAMs ⋮ On the complexity of finding a local maximum of functions on discrete planar subsets ⋮ A tight relationship between generic oracles and type-2 complexity theory ⋮ Structural properties for feasibly computable classes of type two ⋮ On (simple) decision tree rank ⋮ Time and space complexity of deterministic and nondeterministic decision trees ⋮ Exact learning of multitrees and almost-trees using path queries ⋮ Unnamed Item ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Separation Between Deterministic and Randomized Query Complexity ⋮ Arthur-Merlin games in Boolean decision trees ⋮ Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ On random oracle separations ⋮ Separating complexity classes with tally oracles ⋮ Helping by unambiguous computation and probabilistic computation ⋮ Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority ⋮ Polynomial-time compression ⋮ Quadratically tight relations for randomized query complexity ⋮ Improved bounds for the randomized decision tree Complexity of recursive majority ⋮ The Dual BKR Inequality and Rudich's Conjecture ⋮ The relative complexity of NP search problems ⋮ Randomized Boolean decision trees: Several remarks ⋮ On the P versus NP intersected with co-NP question in communication complexity ⋮ Complexity measures and decision tree complexity: a survey.
Cites Work
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Bounded query machines: on NP and PSPACE
- Bounded query machines: on NP( ) and NPQUERY( )
- Parity, circuits, and the polynomial-time hierarchy
- Quantitative Relativizations of Complexity Classes
- A Note on Randomized Polynomial Time
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Every Prime Has a Succinct Certificate
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- The knowledge complexity of interactive proof-systems
This page was built for publication: Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
