Sublogarithmic $\sum _2$-space is not closed under complement and other separation results

DOI10.1051/ita/1993270403491zbMath0804.68047OpenAlexW123519388MaRDI QIDQ3142269

Viliam Geffert

Publication date: 15 November 1993

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92456

zbMATH Keywords

complexity classesspace complexityalternating Turing machine

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

A hierarchy that does not collapse : alternations in low level space ⋮ Bridging across the \(\log(n)\) space frontier ⋮ For completeness, sublogarithmic space is no space.

Cites Work

• Some observations concerning alternating Turing machines using small space
• The method of forced enumeration for nondeterministic automata
• \(\Sigma_ 2SPACE(n)\) is closed under complement
• The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
• Halting space-bounded computations
• Space bounded computations: Review and new separation results
• Space bounds for processing contentless inputs
• Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
• Nondeterministic Space is Closed under Complementation
• Alternation
• Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Sublogarithmic $\sum _2$-space is not closed under complement and other separation results