On Languages with Very High Space-Bounded Kolmogorov Complexity

DOI10.1137/0222029zbMath0770.68053OpenAlexW2075130353MaRDI QIDQ4032946

Ronald V. Book, Jack H. Lutz

Publication date: 17 May 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0222029

zbMATH Keywords

Kolmogorov complexitysparse setsexponential spacebounded truth- table reducible

Mathematics Subject Classification ID

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

Related Items (1)

Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity

This page was built for publication: On Languages with Very High Space-Bounded Kolmogorov Complexity