Resolution of Hartmanis' conjecture for NL-hard sparse sets

DOI10.1016/S0304-3975(99)00234-0zbMath0945.68102OpenAlexW2081315430WikidataQ122956100 ScholiaQ122956100MaRDI QIDQ1575434

N. Delaunay

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

zbMATH Keywords

circuit complexitysparse setsisomorphism conjecturealgebraic computationnondeterministic space

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Unnamed Item ⋮ The enumerability of P collapses P to NC

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