Cook reducibility is faster than Karp reducibility in NP (Q751812): Difference between revisions

@@ Property / cites work @@
+The complexity of theorem-proving procedures
@@ Property / cites work: The complexity of theorem-proving procedures / rank @@
+Normal rank
@@ Property / cites work @@
+A hierarchy for nondeterministic time complexity
@@ Property / cites work: A hierarchy for nondeterministic time complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Honest polynomial degrees and \(P=?NP\)
@@ Property / cites work: Honest polynomial degrees and \(P=?NP\) / rank @@
+Normal rank
@@ Property / cites work @@
+Minimal degrees for polynomial reducibilities
@@ Property / cites work: Minimal degrees for polynomial reducibilities / rank @@
+Normal rank
@@ Property / cites work @@
+Q3862379
@@ Property / cites work: Q3862379 / rank @@
+Normal rank
@@ Property / cites work @@
+Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
+Normal rank
@@ Property / cites work @@
+Q4142699
@@ Property / cites work: Q4142699 / rank @@
+Normal rank
@@ Property / cites work @@
+On one-way functions and polynomial-time isomorphisms
+Normal rank
@@ Property / cites work @@
+Completeness, Approximation and Density
@@ Property / cites work: Completeness, Approximation and Density / rank @@
+Normal rank
@@ Property / cites work @@
+Collapsing degrees
@@ Property / cites work: Collapsing degrees / rank @@
+Normal rank
@@ Property / cites work @@
+A comparison of polynomial time reducibilities
@@ Property / cites work: A comparison of polynomial time reducibilities / rank @@
+Normal rank
@@ Property / cites work @@
+Q3915990
@@ Property / cites work: Q3915990 / rank @@
+Normal rank
@@ Property / cites work @@
+On the density of honest subrecursive classes
@@ Property / cites work: On the density of honest subrecursive classes / rank @@
+Normal rank
@@ Property / cites work @@
+A Classification of the Recursive Functions
@@ Property / cites work: A Classification of the Recursive Functions / rank @@
+Normal rank
@@ Property / cites work @@
+Reductions among polynomial isomorphism types
@@ Property / cites work: Reductions among polynomial isomorphism types / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of unique solutions
@@ Property / cites work: On the complexity of unique solutions / rank @@
+Normal rank
@@ Property / cites work @@
+Recursively enumerable sets of positive integers and their decision problems
+Normal rank
@@ Property / cites work @@
+Q5573961
@@ Property / cites work: Q5573961 / rank @@
+Normal rank
@@ Property / cites work @@
+P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
+Normal rank
@@ Property / cites work @@
+Reductions on NP and p-selective sets
@@ Property / cites work: Reductions on NP and p-selective sets / rank @@
+Normal rank
@@ Property / cites work @@
+Q3819052
@@ Property / cites work: Q3819052 / rank @@
+Normal rank
@@ Property / cites work @@
+A comparison of polynomial time completeness notions
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0022-0000(90)90026-h
+Normal rank
@@ Property / OpenAlex ID @@
+W1985343313
@@ Property / OpenAlex ID: W1985343313 / rank @@
+Normal rank