Query complexity, or why is it difficult to separate $NP^ A\cap coNP^ A$ from $P^ A$ by random oracles A? (Q912625): Difference between revisions

@@ Property / cites work @@
+Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
+Normal rank
@@ Property / cites work @@
+Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
+Normal rank
@@ Property / cites work @@
+Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
+Normal rank
@@ Property / cites work @@
+Bounded query machines: on NP and PSPACE
@@ Property / cites work: Bounded query machines: on NP and PSPACE / rank @@
+Normal rank
@@ Property / cites work @@
+Quantitative Relativizations of Complexity Classes
+Normal rank
@@ Property / cites work @@
+Bounded query machines: on NP( ) and NPQUERY( )
@@ Property / cites work: Bounded query machines: on NP( ) and NPQUERY( ) / rank @@
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+The knowledge complexity of interactive proof-systems
+Normal rank
@@ Property / cites work @@
+A Note on Randomized Polynomial Time
@@ Property / cites work: A Note on Randomized Polynomial Time / rank @@
+Normal rank
@@ Property / cites work @@
+Every Prime Has a Succinct Certificate
@@ Property / cites work: Every Prime Has a Succinct Certificate / rank @@
+Normal rank

Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? (Q912625): Difference between revisions