Resolution of Hartmanis' conjecture for NL-hard sparse sets
From MaRDI portal
Publication:1575434
DOI10.1016/S0304-3975(99)00234-0zbMath0945.68102OpenAlexW2081315430WikidataQ122956100 ScholiaQ122956100MaRDI QIDQ1575434
Publication date: 21 August 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00234-0
Related Items
Cites Work
- Turing machines that take advice
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Inverting a Vandermonde matrix in minimum parallel time
- On log-tape isomorphisms of complete sets
- Maze recognizing automata and nondeterministic tape complexity
- Parity, circuits, and the polynomial-time hierarchy
- Constant Depth Reducibility
- Very Fast Parallel Polynomial Arithmetic
- Languages that Capture Complexity Classes
- Nondeterministic Space is Closed under Complementation
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- On the existence of hard sparse sets under weak reductions
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item