For completeness, sublogarithmic space is no space.

DOI10.1016/S0020-0190(01)00296-4MaRDI QIDQ1853022zbMATH OpenOpenAlexFDO

Authors 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

CompletenessComputational complexityIsomorphismsSublogarithmic reductions

Mathematics Subject Classification ID

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

Recommendations

• The alternation hierarchy for sublogarithmic space is infinite
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• scientific article; zbMATH DE number 7052231
• Alternating space is closed under complement and other simulations for sublogarithmic space
• Spaces with no uncountable submetrisable subsets
• scientific article; zbMATH DE number 1759437
• A Completely Finitistic Space is Finite-Dimensional
• L-space without any uncountable 0-dimensiolan subspace
• Choiceless Logarithmic Space
• A Lindelöf space with no Lindelöf subspace of size $\aleph \textunderscore 1$

Cites work

• scientific article; zbMATH DE number 512810 (Why is no real title available?)
• scientific article; zbMATH DE number 512811 (Why is no real title available?)
• scientific article; zbMATH DE number 512825 (Why is no real title available?)
• scientific article; zbMATH DE number 1559593 (Why is no real title available?)
• scientific article; zbMATH DE number 3319549 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• A hierarchy that does not collapse : alternations in low level space
• Complete Problems and Strong Polynomial Reducibilities
• Computational Complexity and the Existence of Complexity Gaps
• Isomorphisms and 1-L reductions
• Nondeterministic Space is Closed under Complementation
• ON THE ISOMORPHISM CONJECTURE FOR 2-DFA REDUCTIONS
• On log-tape isomorphisms of complete sets
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Some Results on Tape-Bounded Turing Machines
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• The Sublogarithmic Alternating Space World
• The alternation hierarchy for sublogarithmic space is infinite
• The method of forced enumeration for nondeterministic automata

Cited in

(3)

• 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
• The alternation hierarchy for sublogarithmic space is infinite

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853022)