UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n)
From MaRDI portal
Publication:5495427
DOI10.1142/S0129054113400376zbMath1298.68134MaRDI QIDQ5495427
Dana Pardubská, Viliam Geffert
Publication date: 4 August 2014
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (4)
Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space
Cites Work
- Space bounded computations: Review and new separation results
- Bits and relative order from residues, space efficiently
- Space hierarchy theorem revised.
- Relationships between nondeterministic and deterministic tape complexities
- Alternation
- ${\text{ASPACE}}(o(\log \log n))$ is Regular
- The Sublogarithmic Alternating Space World
This page was built for publication: UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n)
