Compressibility and uniform complexity

DOI10.1016/S0020-0190(97)00070-7zbMath1337.68141OpenAlexW2007616727MaRDI QIDQ287086

Montserrat Hermo

Publication date: 26 May 2016

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00070-7

zbMATH Keywords

computational complexityKolmogorov complexitycompressibilitymulti-tape Turing machineuniform complexity

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• On the notion of infinite pseudorandom sequences
• A variant of the Kolmogorov concept of complexity
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Compressibility and uniform complexity