scientific article; zbMATH DE number 1072535

MaRDI QIDQ4359462zbMATH OpenFDO

Authors Maciej Liśkiewicz, Rüdiger Reischuk

Publication date 7 January 1998

zbMATH Keywords

Turing machinesspace complexity classes

Mathematics Subject Classification ID

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

Recommendations

• The Sublogarithmic Alternating Space World
• scientific article; zbMATH DE number 512811
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results

Cited in

(17)

• On small space complexity classes of stochastic Turing machines and Arthur-Merlin-games
• Regressive computations characterize logarithmic space
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• A survey of space complexity
• On the structure of log-space probabilistic complexity classes (extended abstract)
• An alternating hierarchy for finite automata
• scientific article; zbMATH DE number 2040917 (Why is no real title available?)
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
• Space hierarchy results for randomized and other semantic models
• Computation with Narrow CTCs
• scientific article; zbMATH DE number 17793 (Why is no real title available?)
• scientific article; zbMATH DE number 2172794 (Why is no real title available?)
• The Sublogarithmic Alternating Space World
• Lower time bounds for randomized computation
• Bridging across the \(\log (n)\) space frontier
• Complement for two-way alternating automata
• 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 Q4359462)