Some notes on strong and weak log log n space complexity

DOI10.1016/0020-0190(89)90163-4zbMath0682.68063OpenAlexW2065008672MaRDI QIDQ1824397

Andrzej Szepietowski

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90163-4

zbMATH Keywords

complexityTuring machineweak and strong mode

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (2)

A survey of space complexity ⋮ Bridging across the \(\log(n)\) space frontier

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
• Some observations concerning alternating Turing machines using small space
• Remarks on languages acceptable in log log n space
• Halting space-bounded computations
• Space bounds for processing contentless inputs

This page was built for publication: Some notes on strong and weak log log n space complexity