Some notes on strong and weak log log n space complexity
From MaRDI portal
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
Cites work
- scientific article; zbMATH DE number 3917711 (Why is no real title available?)
- scientific article; zbMATH DE number 3723863 (Why is no real title available?)
- scientific article; zbMATH DE number 3428547 (Why is no real title available?)
- scientific article; zbMATH DE number 3363526 (Why is no real title available?)
- Halting space-bounded computations
- 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
- Some observations concerning alternating Turing machines using small space
- Space bounds for processing contentless inputs
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)
