For completeness, sublogarithmic space is no space.
From MaRDI portal
Publication:1853022
DOI10.1016/S0020-0190(01)00296-4zbMath1043.68062OpenAlexW1976967842MaRDI QIDQ1853022
Publication date: 21 January 2003
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00296-4
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Fooling Turing machines with sublogarithmic space: a note on `For completeness, sublogarithmic space is no space' by M. Agrawal, Reductions in circuit complexity: An isomorphism theorem and a gap theorem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The method of forced enumeration for nondeterministic automata
- Isomorphisms and 1-L reductions
- On log-tape isomorphisms of complete sets
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem
- The alternation hierarchy for sublogarithmic space is infinite
- ON THE ISOMORPHISM CONJECTURE FOR 2-DFA REDUCTIONS
- Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
- Nondeterministic Space is Closed under Complementation
- Complete Problems and Strong Polynomial Reducibilities
- ${\text{ASPACE}}(o(\log \log n))$ is Regular
- A hierarchy that does not collapse : alternations in low level space
- The Sublogarithmic Alternating Space World
- Some Results on Tape-Bounded Turing Machines
- Computational Complexity and the Existence of Complexity Gaps
