List approximation for increasing Kolmogorov complexity

DOI10.4230/LIPICS.STACS.2017.58MaRDI QIDQ4636659zbMATH OpenOpenAlexFDO

Authors Marius Zimand

Publication date 19 April 2018

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

zbMATH Keywords

Kolmogorov complexitylist approximationrandomness extractor

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithms on strings (68W32)

Abstract: It is impossible to effectively modify a string in order to increase its Kolmogorov complexity. But is it possible to construct a few strings, not longer than the input string, so that most of them have larger complexity? We show that the answer is yes. We present an algorithm that on input a string $x$ of length $n$ returns a list with $O(n^2)$ many strings, all of length $n$, such that 99% of them are more complex than $x$, provided the complexity of $x$ is less than $n-loglogn-O(1)$. We obtain similar results for other parameters, including a polynomial-time construction.

Recommendations

• STACS 2005
• Short lists for shortest descriptions in short time
• On approximate uncomputability of the Kolmogorov complexity function
• Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity
• A safe approximation for Kolmogorov complexity

Cited in

(4)

• Towards a nonlinear Schwarz's list
• Short lists for shortest descriptions in short time
• Short lists with short programs in short time -- a short proof
• On the Complexity of Approximate Sum of Sorted List

This page was built for publication: List approximation for increasing Kolmogorov complexity

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