UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n)

DOI10.1142/S0129054113400376zbMath1298.68134MaRDI QIDQ5495427

Viliam Geffert, Dana Pardubská

Publication date: 4 August 2014

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

complexity theory; unary languages; sublogarithmic space; binary languages

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)