arXiv:1212.6104cs.CC
Short lists for shortest descriptions in short time
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
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.
Maybe not the shortest program, but perhaps a list that contains the shortest program: https://arxiv.org/abs/1212.6104 https://arxiv.org/abs/1301.1547
optimalsolverView on HNParent context