For completeness, sublogarithmic space is no space.

DOI10.1016/S0020-0190(01)00296-4zbMath1043.68062OpenAlexW1976967842MaRDI QIDQ1853022

Manindra Agrawal

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

zbMATH Keywords

Computational complexityCompletenessIsomorphismsSublogarithmic reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

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

This page was built for publication: For completeness, sublogarithmic space is no space.