Relativized isomorphisms of NP-complete sets (Q687510): Difference between revisions

@@ Property / cites work @@
+Diagonalizations over polynomial time computable sets
+Normal rank
@@ Property / cites work @@
+Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy and sparse oracles
@@ Property / cites work: The polynomial-time hierarchy and sparse oracles / rank @@
+Normal rank
@@ Property / cites work @@
+Bi-immune sets for complexity classes
@@ Property / cites work: Bi-immune sets for complexity classes / rank @@
+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 @@
+Q4131649
@@ Property / cites work: Q4131649 / rank @@
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Propositional representation of arithmetic proofs (Preliminary Version)
+Normal rank
@@ Property / cites work @@
+Q4230324
@@ Property / cites work: Q4230324 / rank @@
+Normal rank
@@ Property / cites work @@
+Are there interactive protocols for co-NP languages?
+Normal rank
@@ Property / cites work @@
+One-way functions and the nonisomorphism of NP-complete sets
+Normal rank
@@ Property / cites work @@
+On one-way functions and polynomial-time isomorphisms
+Normal rank
@@ Property / cites work @@
+Collapsing degrees
@@ Property / cites work: Collapsing degrees / rank @@
+Normal rank
@@ Property / cites work @@
+The isomorphism conjecture fails relative to a random oracle
+Normal rank