Space hierarchy theorem revised

DOI10.1007/3-540-44683-4_34MaRDI QIDQ4785461zbMATH OpenFDO

Authors Viliam Geffert

Publication date 25 February 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-44683-4_34

zbMATH Keywords

computational complexityspace complexity

Mathematics Subject Classification ID

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

Recommendations

• Space hierarchy theorem revised.
• scientific article; zbMATH DE number 2172793
• Sublogarithmic Bounds on Space and Reversals
• Turing machines with sublogarithmic space
• scientific article; zbMATH DE number 2172794

Cited in

(5)

• On a complexity hierarchy between L and NL
• On space functions fully constructed by two-dimensional Turing machines
• Space hierarchy theorem revised.
• scientific article; zbMATH DE number 2172793 (Why is no real title available?)
• Unary coded NP-complete languages in \(\mathrm{ASpace}(\log \log n)\)

This page was built for publication: Space hierarchy theorem revised

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