Time-bounded incompressibility of compressible strings and sequences

DOI10.1016/J.IPL.2009.06.013zbMath1202.68213OpenAlexW2152025308MaRDI QIDQ989573

Edgar G. Daylight, Wouter M. Koolen, Paul M. B. Vitányi

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/14816

zbMATH Keywords

computational complexityKolmogorov complexitycompressibilityBarzdins's lemmafinite strings and infinite sequencestime-bounded incompressibility

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Unnamed Item
• Computational depth: Concept and applications
• A variant of the Kolmogorov concept of complexity
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Time-bounded incompressibility of compressible strings and sequences