scientific article; zbMATH DE number 512811

MaRDI QIDQ4281504zbMATH OpenFDO

Authors Maciej Liśkiewicz, Rüdiger Reischuk

Publication date 13 November 1994

zbMATH Keywords

separation of complexity classesalternating space hierarchy

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• The Sublogarithmic Alternating Space World

Cited in

(13)

• A hierarchy that does not collapse : alternations in low level space
• A note on multi-inkdot nondeterministic Turing machines with small space
• The alternation hierarchy for sublogarithmic space is infinite
• Inductive counting below LOGSPACE
• Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
• On a complexity hierarchy between L and NL
• For completeness, sublogarithmic space is no space.
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• Bridging across the \(\log(n)\) space frontier
• Alternating space is closed under complement and other simulations for sublogarithmic space
• scientific article; zbMATH DE number 2172794 (Why is no real title available?)
• The Sublogarithmic Alternating Space World
• Turing machines with sublogarithmic space

This page was built for publication:

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