Some notes on strong and weak log log n space complexity

DOI10.1016/0020-0190(89)90163-4zbMATH Open0682.68063OpenAlexW2065008672MaRDI QIDQ1824397FDOQ1824397

Authors: 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

Recommendations

• scientific article; zbMATH DE number 8798
• Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
• If deterministic and nondeterministic space complexities are equal for \(\log \log n\) then they are also equal for \(\log n\)
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
• Remarks on languages acceptable in log log n space

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)

Cites Work

• Title not available (Why is that?)
• Halting space-bounded computations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Space bounds for processing contentless inputs
• Some observations concerning alternating Turing machines using small space
• Remarks on languages acceptable in log log n space
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n

Cited In (5)

• Bridging across the \(\log(n)\) space frontier
• If deterministic and nondeterministic space complexities are equal for \(\log \log n\) then they are also equal for \(\log n\)
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
• Remarks on languages acceptable in log log n space
• A survey of space complexity

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

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