Space-efficient recognition of sparse self-reducible languages (Q1337147): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Limitations of the upward separation technique
@@ Property / cites work: Limitations of the upward separation technique / rank @@
+Normal rank
@@ Property / cites work @@
+Q4281491
@@ Property / cites work: Q4281491 / rank @@
+Normal rank
@@ Property / cites work @@
+Self-reducibility
@@ Property / cites work: Self-reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Q4160434
@@ Property / cites work: Q4160434 / rank @@
+Normal rank
@@ Property / cites work @@
+On Relating Time and Space to Size and Depth
@@ Property / cites work: On Relating Time and Space to Size and Depth / rank @@
+Normal rank
@@ Property / cites work @@
+The recognition of deterministic CFLs in small time and space
+Normal rank
@@ Property / cites work @@
+On time-space classes and their relation to the theory of real addition
+Normal rank
@@ Property / cites work @@
+A taxonomy of problems with fast parallel algorithms
+Normal rank
@@ Property / cites work @@
+A Note on Sparse Complete Sets
@@ Property / cites work: A Note on Sparse Complete Sets / rank @@
+Normal rank
@@ Property / cites work @@
+On log-tape isomorphisms of complete sets
@@ Property / cites work: On log-tape isomorphisms of complete sets / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse sets in NP-P: EXPTIME versus NEXPTIME
@@ Property / cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME / rank @@
+Normal rank
@@ Property / cites work @@
+Q5636862
@@ Property / cites work: Q5636862 / rank @@
+Normal rank
@@ Property / cites work @@
+Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
+Normal rank
@@ Property / cites work @@
+On Circuit-Size Complexity and the Low Hierarchy in NP
+Normal rank
@@ Property / cites work @@
+Relativization of questions about log space computability
+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 @@
+Q5180413
@@ Property / cites work: Q5180413 / rank @@
+Normal rank
@@ Property / cites work @@
+Hard promise problems and nonuniform complexity
@@ Property / cites work: Hard promise problems and nonuniform complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Self-reducible sets of small density
@@ Property / cites work: Self-reducible sets of small density / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
+Normal rank
@@ Property / cites work @@
+Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
+Normal rank
@@ Property / cites work @@
+On uniform circuit complexity
@@ Property / cites work: On uniform circuit complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Relationships between nondeterministic and deterministic tape complexities
+Normal rank
@@ Property / cites work @@
+A low and a high hierarchy within NP
@@ Property / cites work: A low and a high hierarchy within NP / rank @@
+Normal rank
@@ Property / cites work @@
+On the Tape Complexity of Deterministic Context-Free Languages
+Normal rank
@@ Property / cites work @@
+Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
+Normal rank
@@ Property / cites work @@
+On polynomial time one-truth-table reducibility to a sparse set
+Normal rank
@@ Property / cites work @@
+On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/bf01206639
+Normal rank
@@ Property / OpenAlex ID @@
+W2015323017
@@ Property / OpenAlex ID: W2015323017 / rank @@
+Normal rank