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

@@ Property / DOI @@
-.1006/jcss.1998.1575
@@ Property / DOI: 10.1006/jcss.1998.1575 / rank @@
-Normal rank
@@ Property / author @@
-P. W. Beame
@@ Property / author: P. W. Beame / rank @@
-Normal rank
@@ Property / author @@
-Stephen A. Cook
@@ Property / author: Stephen A. Cook / rank @@
-Normal rank
@@ Property / author @@
+P. W. Beame
@@ Property / author: P. W. Beame / rank @@
+Normal rank
@@ Property / author @@
+Stephen A. Cook
@@ Property / author: Stephen A. Cook / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1006/jcss.1998.1575
+Normal rank
@@ Property / OpenAlex ID @@
+W2037028865
@@ Property / OpenAlex ID: W2037028865 / rank @@
+Normal rank
@@ 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
@@ Property / DOI @@
+.1006/JCSS.1998.1575
@@ Property / DOI: 10.1006/JCSS.1998.1575 / rank @@
+Normal rank