On Languages with Very High Space-Bounded Kolmogorov Complexity

DOI10.1137/0222029MaRDI QIDQ4032946zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 3988704
• Power from Random Strings
• scientific article; zbMATH DE number 107775
• Randomness is hard
• Mathematical Foundations of Computer Science 2004

Cited in

(8)

• scientific article; zbMATH DE number 3984572 (Why is no real title available?)
• scientific article; zbMATH DE number 3988704 (Why is no real title available?)
• Inequalities for space-bounded Kolmogorov complexity
• Mathematical Foundations of Computer Science 2004
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• A new complete language for DSPACE(log n)
• Refined Bounds on Kolmogorov Complexity for ω-Languages
• Enumerations of the Kolmogorov function

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4032946)