Cook versus Karp-Levin: Separating completeness notions if NP is not small (Q671427): Difference between revisions

@@ Property / Wikidata QID @@
+Q60578985
@@ Property / Wikidata QID: Q60578985 / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2080139332
@@ Property / OpenAlex ID: W2080139332 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Decision Versus Search
@@ Property / cites work: The Complexity of Decision Versus Search / rank @@
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Tally languages and complexity classes
@@ Property / cites work: Tally languages and complexity classes / rank @@
+Normal rank
@@ Property / cites work @@
+Completeness for nondeterministic complexity classes
+Normal rank
@@ Property / cites work @@
+Q4138187
@@ Property / cites work: Q4138187 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity and Distribution of Hard Problems
@@ Property / cites work: The Complexity and Distribution of Hard Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q4142699
@@ Property / cites work: Q4142699 / rank @@
+Normal rank
@@ Property / cites work @@
+Completeness, Approximation and Density
@@ Property / cites work: Completeness, Approximation and Density / 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 @@
+Cook reducibility is faster than Karp reducibility in NP
+Normal rank
@@ Property / cites work @@
+Almost everywhere high nonuniform complexity
@@ Property / cites work: Almost everywhere high nonuniform complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Measure, Stochasticity, and the Density of Hard Languages
+Normal rank
@@ Property / cites work @@
+Almost every set in exponential time is P-bi-immune
+Normal rank
@@ Property / cites work @@
+Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
+Normal rank
@@ Property / cites work @@
+The density and complexity of polynomial cores for intractable sets
+Normal rank
@@ Property / cites work @@
+Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung
+Normal rank
@@ Property / cites work @@
+A unified approach to the definition of random sequences
+Normal rank
@@ Property / cites work @@
+Q5616138
@@ Property / cites work: Q5616138 / rank @@
+Normal rank
@@ Property / cites work @@
+Process complexity and effective random tests
@@ Property / cites work: Process complexity and effective random tests / 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 @@
+A comparison of polynomial time completeness notions
+Normal rank
@@ Property / cites work @@
+On polynomial-time Turing and many-one completeness in PSPACE
+Normal rank
@@ Property / DBLP publication ID @@
+journals/tcs/LutzM96
@@ Property / DBLP publication ID: journals/tcs/LutzM96 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:671427