Short lists with short programs in short time

DOI10.1007/S00037-017-0154-2MaRDI QIDQ1745959zbMATH OpenOpenAlexFDO

Authors B. Bauwens, Anton Makhlin, Marius Zimand, Nikolai K. Vereshchagin

Publication date 18 April 2018

Published in Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

Kolmogorov complexityexpander graphonline matchinglist-approximator

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Complexity of computation (including implicit computational complexity) (03D15)

Abstract: Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any standard Turing machine, it is possible to compute in polynomial time on input $x$ a list of polynomial size guaranteed to contain a O$(log|x|)$-short program for $x$. We also show that there exists a computable function that maps every $x$ to a list of size $|x{|}^2$ containing a O$(1)$-short program for $x$. This is essentially optimal because we prove that for each such function there is a $c$ and infinitely many $x$ for which the list has size at least $c|x{|}^2$. Finally we show that for some standard machines, computable functions generating lists with $0$-short programs, must have infinitely often list sizes proportional to $2^{|x|}$.

Recommendations

• Short lists with short programs in short time -- a short proof
• Short lists with short programs from programs of functions and strings
• On the problem of finding minimal programs for tables
• Short lists for shortest descriptions in short time
• Searching for shortest and least programs

Cites work

• scientific article; zbMATH DE number 5605130 (Why is no real title available?)
• scientific article; zbMATH DE number 3492569 (Why is no real title available?)
• Algorithmic minimal sufficient statistics: a new approach
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity
• Conditional complexity and codes
• Enumerations of the Kolmogorov function
• Extracting Kolmogorov complexity with applications to dimension zero-one laws
• Game arguments in computability theory and algorithmic information theory
• Generating Kolmogorov random strings from sources with limited independence
• Kolmogorov complexity in randomness extraction
• Lossless condensers, unbalanced expanders, and extractors
• On Representatives of Subsets
• On a problem of K. Zarankiewicz
• On some games which are relevant to the theory of recursively enumerable sets
• Optimal enumerations and optimal gödel numberings
• Resource-bounded Kolmogorov complexity revisited
• Short lists for shortest descriptions in short time
• Short lists with short programs in short time
• Short lists with short programs in short time -- a short proof
• Space-bounded Kolmogorov extractors

Cited in

(15)

• Coding with minimal programs
• Online and Offline Access to Short Lists
• Algorithmic minimal sufficient statistics: a new approach
• scientific article; zbMATH DE number 4072942 (Why is no real title available?)
• On optimal language compression for sets in PSPACE/poly
• On approximate decidability of minimal programs
• On the problem of finding minimal programs for tables
• Short lists with short programs in short time
• Short lists for shortest descriptions in short time
• Topological arguments for Kolmogorov complexity
• Searching for shortest and least programs
• Enumerations including laconic enumerators
• Short lists with short programs from programs of functions and strings
• Short lists with short programs in short time -- a short proof
• THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS

This page was built for publication: Short lists with short programs in short time

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