Time-bounded incompressibility of compressible strings and sequences

DOI10.1016/J.IPL.2009.06.013zbMATH Open1202.68213OpenAlexW2152025308MaRDI QIDQ989573FDOQ989573

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

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

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

• An introduction to Kolmogorov complexity and its applications
• A variant of the Kolmogorov concept of complexity
• Title not available (Why is that?)
• Computational depth: Concept and applications
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets

Cited In (3)

• Compressibility and uniform complexity
• Compressibility of Deterministic and Random Infinite Sequences
• Title not available (Why is that?)

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)