Space-efficient recognition of sparse self-reducible languages
From MaRDI portal
Publication:1337147
DOI10.1007/BF01206639zbMath0812.68073OpenAlexW2015323017MaRDI QIDQ1337147
Ogihara, Mitsunori, Hemaspaandra, Lane A.
Publication date: 14 May 1995
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01206639
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (3)
Unnamed Item ⋮ The Power of Self-Reducibility: Selectivity, Information, and Approximation ⋮ Sparse hard sets for P: Resolution of a conjecture of Hartmanis
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A low and a high hierarchy within NP
- On uniform circuit complexity
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On polynomial time one-truth-table reducibility to a sparse set
- A comparison of polynomial time reducibilities
- On log-tape isomorphisms of complete sets
- Hard promise problems and nonuniform complexity
- Relationships between nondeterministic and deterministic tape complexities
- Self-reducibility
- A Note on Sparse Complete Sets
- Self-reducible sets of small density
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
- The recognition of deterministic CFLs in small time and space
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Limitations of the upward separation technique
- On Circuit-Size Complexity and the Low Hierarchy in NP
- A taxonomy of problems with fast parallel algorithms
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Relativization of questions about log space computability
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- On Relating Time and Space to Size and Depth
- On the Tape Complexity of Deterministic Context-Free Languages
- On time-space classes and their relation to the theory of real addition
This page was built for publication: Space-efficient recognition of sparse self-reducible languages
