The relative complexity of NP search problems (Q1273858): Difference between revisions

@@ Property / cites work @@
+A tight relationship between generic oracles and type-2 complexity theory
+Normal rank
@@ Property / cites work @@
+Self-witnessing polynomial-time complexity and prime factorization
+Normal rank
@@ Property / cites work @@
+One-way functions and the nonisomorphism of NP-complete sets
+Normal rank
@@ Property / cites work @@
+How easy is local search?
@@ Property / cites work: How easy is local search? / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of the parity argument and other inefficient proofs of existence
+Normal rank
@@ Property / cites work @@
+Every Prime Has a Succinct Certificate
@@ Property / cites work: Every Prime Has a Succinct Certificate / rank @@
+Normal rank
@@ Property / cites work @@
+Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
+Normal rank
@@ Property / cites work @@
+Complexity for type-2 relations
@@ Property / cites work: Complexity for type-2 relations / rank @@
+Normal rank