Time-bounded incompressibility of compressible strings and sequences

DOI10.1016/J.IPL.2009.06.013MaRDI QIDQ989573zbMATHOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1048038
• Compressibility and uniform complexity
• scientific article; zbMATH DE number 1335898
• Logical Approaches to Computational Barriers
• Randomness is hard

Cites work

• scientific article; zbMATH DE number 3307567 (Why is no real title available?)
• A variant of the Kolmogorov concept of complexity
• An introduction to Kolmogorov complexity and its applications
• Computational depth: Concept and applications
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets

Cited in

(3)

• Compressibility of Deterministic and Random Infinite Sequences
• Compressibility and uniform complexity
• scientific article; zbMATH DE number 1421006 (Why is no real title available?)

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

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