Time-bounded incompressibility of compressible strings and sequences

DOI10.1016/J.IPL.2009.06.013MaRDI QIDQ989573zbMATH OpenOpenAlexFDO

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

Barzdins's lemmacompressibilitycomputational complexityfinite strings and infinite sequencesKolmogorov complexitytime-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

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

Cited in

(4)

• Compressibility and uniform complexity
• scientific article; zbMATH DE number 1048038 (Why is no real title available?)
• Compressibility of Deterministic and Random Infinite Sequences
• 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)