Nondeterministic computations in sublogarithmic space and space constructibility

DOI10.1007/BFB0032026MaRDI QIDQ4038686zbMATH OpenFDO

Authors Viliam Geffert

Publication date 18 May 1993

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

Full work available at URL https://doi.org/10.1007/BFB0032026

zbMATH Keywords

nondeterministic Turing machinesnondeterministically space constructible functionsspace complexity theory

Mathematics Subject Classification ID

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

Recommendations

• Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
• Bridging across the (n) space frontier
• Space bounded computations: Review and new separation results
• Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties

Cited in

(9)

• Space bounded computations: Review and new separation results
• A survey of space complexity
• Bridging across the (n) space frontier
• The alternation hierarchy for sublogarithmic space is infinite
• scientific article; zbMATH DE number 3883610 (Why is no real title available?)
• scientific article; zbMATH DE number 4045156 (Why is no real title available?)
• scientific article; zbMATH DE number 17793 (Why is no real title available?)
• Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
• Sublogarithmic Bounds on Space and Reversals

This page was built for publication: Nondeterministic computations in sublogarithmic space and space constructibility

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