Sparse hard sets for P: Resolution of a conjecture of Hartmanis (Q1288202): Difference between revisions

@@ Property / DOI @@
-.1006/jcss.1998.1615
@@ Property / DOI: 10.1006/jcss.1998.1615 / rank @@
-Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W1985877037
@@ Property / OpenAlex ID: W1985877037 / rank @@
+Normal rank
@@ Property / cites work @@
+An Optimal Parallel Algorithm for Formula Evaluation
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Fast parallel matrix and GCD computations
@@ Property / cites work: Fast parallel matrix and GCD computations / rank @@
+Normal rank
@@ Property / cites work @@
+Q3719722
@@ Property / cites work: Q3719722 / rank @@
+Normal rank
@@ Property / cites work @@
+On the existence of hard sparse sets under weak reductions
+Normal rank
@@ Property / cites work @@
+Q4364576
@@ Property / cites work: Q4364576 / rank @@
+Normal rank
@@ Property / cites work @@
+Constant Depth Reducibility
@@ Property / cites work: Constant Depth Reducibility / rank @@
+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 @@
+Q4198056
@@ Property / cites work: Q4198056 / 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 @@
+Space-efficient recognition of sparse self-reducible languages
+Normal rank
@@ Property / cites work @@
+Relating Equivalence and Reducibility to Sparse Sets
+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 @@
+A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
+Normal rank
@@ Property / cites work @@
+Small-Bias Probability Spaces: Efficient Constructions and Applications
+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 @@
+Q3815544
@@ Property / cites work: Q3815544 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3946078
@@ Property / cites work: Q3946078 / rank @@
+Normal rank
@@ Property / DBLP publication ID @@
+journals/jcss/CaiS99
@@ Property / DBLP publication ID: journals/jcss/CaiS99 / rank @@
+Normal rank
@@ Property / DOI @@
+.1006/JCSS.1998.1615
@@ Property / DOI: 10.1006/JCSS.1998.1615 / rank @@
+Normal rank