Structural complexity theory: Recent surprises (Q5056087): Difference between revisions

@@ Property / cites work @@
+Non-deterministic exponential time has two-prover interactive protocols
+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 @@
+Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Q3773331
@@ Property / cites work: Q3773331 / rank @@
+Normal rank
@@ Property / cites work @@
+Are there interactive protocols for co-NP languages?
+Normal rank
@@ Property / cites work @@
+Computational Complexity of Probabilistic Turing Machines
+Normal rank
@@ Property / cites work @@
+Q3830531
@@ Property / cites work: Q3830531 / rank @@
+Normal rank
@@ Property / cites work @@
+The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+The isomorphism conjecture fails relative to a random oracle
+Normal rank
@@ Property / cites work @@
+Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
+Normal rank