Short lists for shortest descriptions in short time

DOI10.1007/S00037-014-0090-3MaRDI QIDQ475336zbMATHOpenAlexFDO

Authors Jason Teutsch

Publication date 26 November 2014

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.6104

zbMATH Keywords

Kolmogorov complexitybipartite expander graphdisperser graphMuchnik's conditional complexity theoremonline matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: Is it possible to find a shortest description for a binary string? The well-known answer is "no, Kolmogorov complexity is not computable." Faced with this barrier, one might instead seek a short list of candidates which includes a laconic description. Remarkably such approximations exist. This paper presents an efficient algorithm which generates a polynomial-size list containing an optimal description for a given input string. Along the way, we employ expander graphs and randomness dispersers to obtain an Explicit Online Matching Theorem for bipartite graphs and a refinement of Muchnik's Conditional Complexity Theorem. Our main result extends recent work by Bauwens, Mahklin, Vereschchagin, and Zimand.

Recommendations

• Short lists with short programs in short time -- a short proof
• Short lists with short programs in short time
• List approximation for increasing Kolmogorov complexity
• An incomplete set of shortest descriptions

Cites work

• An introduction to Kolmogorov complexity and its applications
• Conditional complexity and codes
• Enumerations of the Kolmogorov function
• Lossless condensers, unbalanced expanders, and extractors
• Resource-bounded Kolmogorov complexity revisited
• Short lists with short programs in short time
• Short lists with short programs in short time -- a short proof
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes

Cited in

(7)

• Enumerations including laconic enumerators
• Online and Offline Access to Short Lists
• On approximate decidability of minimal programs
• List approximation for increasing Kolmogorov complexity
• Short lists with short programs in short time
• Short lists with short programs in short time -- a short proof
• Searching for shortest and least programs

This page was built for publication: Short lists for shortest descriptions in short time

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