Sparse hard sets for P: Resolution of a conjecture of Hartmanis
From MaRDI portal
Publication:1288202
DOI10.1006/jcss.1998.1615zbMath0936.68046OpenAlexW1985877037WikidataQ56092494 ScholiaQ56092494MaRDI QIDQ1288202
Publication date: 11 May 1999
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/1b36604e1da222ae2f6d3b765aaad4df419929bf
Related Items (3)
Complexity of equations over sets of natural numbers ⋮ Separating NE from some nonuniform nondeterministic complexity classes ⋮ On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Turing machines that take advice
- A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On log-tape isomorphisms of complete sets
- Space-efficient recognition of sparse self-reducible languages
- A Note on Sparse Complete Sets
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Constant Depth Reducibility
- A taxonomy of problems with fast parallel algorithms
- Nondeterministic Space is Closed under Complementation
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Relating Equivalence and Reducibility to Sparse Sets
- An Optimal Parallel Algorithm for Formula Evaluation
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- On the existence of hard sparse sets under weak reductions
- Fast parallel matrix and GCD computations
This page was built for publication: Sparse hard sets for P: Resolution of a conjecture of Hartmanis
