Resolution of Hartmanis' conjecture for NL-hard sparse sets (Q1575434): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+On the existence of hard sparse sets under weak reductions
+Normal rank
@@ Property / cites work @@
+Q4359456
@@ Property / cites work: Q4359456 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4252721
@@ Property / cites work: Q4252721 / rank @@
+Normal rank
@@ Property / cites work @@
+Constant Depth Reducibility
@@ Property / cites work: Constant Depth Reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+Very Fast Parallel Polynomial Arithmetic
@@ Property / cites work: Very Fast Parallel Polynomial Arithmetic / rank @@
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+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 @@
+Languages that Capture Complexity Classes
@@ Property / cites work: Languages that Capture Complexity Classes / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterministic Space is Closed under Complementation
+Normal rank
@@ Property / cites work @@
+Turing machines that take advice
@@ Property / cites work: Turing machines that take advice / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
+Normal rank
@@ Property / cites work @@
+Q4252720
@@ Property / cites work: Q4252720 / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
+Normal rank
@@ Property / cites work @@
+Inverting a Vandermonde matrix in minimum parallel time
+Normal rank
@@ Property / cites work @@
+Maze recognizing automata and nondeterministic tape complexity
+Normal rank
@@ Property / cites work @@
+Q4040892
@@ Property / cites work: Q4040892 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3815544
@@ Property / cites work: Q3815544 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3946078
@@ Property / cites work: Q3946078 / rank @@
+Normal rank