If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n

DOI10.1016/0304-3975(90)90008-6zbMath0701.68033OpenAlexW1586252286MaRDI QIDQ914371

Andrzej Szepietowski

Publication date: 1990

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(90)90008-6

zbMATH Keywords

space complexityequality of complexity classesspace function

Mathematics Subject Classification ID

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

Related Items (6)

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Space bounded computations: Review and new separation results ⋮ A survey of space complexity ⋮ Bridging across the \(\log(n)\) space frontier ⋮ Some notes on strong and weak log log n space complexity ⋮ Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space

Cites Work

• Remarks on languages acceptable in log log n space
• Halting space-bounded computations
• Relationships between nondeterministic and deterministic tape complexities
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n