Short lists for shortest descriptions in short time

DOI10.1007/S00037-014-0090-3zbMATH Open1366.68103arXiv1212.6104OpenAlexW2022038544MaRDI QIDQ475336FDOQ475336

Authors: Jason Teutsch 

Publication date: 26 November 2014

Published in: Computational Complexity (Search for Journal in Brave)

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.

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

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
• Variations on Muchnik's conditional complexity theorem
• An incomplete set of shortest descriptions

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)

Cites Work

• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Short lists with short programs in short time
• An introduction to Kolmogorov complexity and its applications
• Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
• Resource-bounded Kolmogorov complexity revisited
• Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization
• Lossless condensers, unbalanced expanders, and extractors
• Short lists with short programs in short time -- a short proof
• Enumerations of the Kolmogorov function
• Conditional complexity and codes
• Variations on Muchnik's conditional complexity theorem

Cited In (7)

• 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
• Searching for shortest and least programs
• Enumerations including laconic enumerators
• Short lists with short programs in short time -- a short proof

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)