scientific article; zbMATH DE number 512811

zbMATH Open0799.68092MaRDI QIDQ4281504FDOQ4281504

Authors: Maciej Liśkiewicz, Rüdiger Reischuk 

Publication date: 13 November 1994

Title of this publication is not available (Why is that?)

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

zbMATH Keywords

separation of complexity classesalternating space hierarchy

Mathematics Subject Classification ID

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

Cited In (13)

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