List approximation for increasing Kolmogorov complexity

DOI10.4230/LIPICS.STACS.2017.58zbMATH Open1402.68110arXiv1609.05984OpenAlexW2963298120MaRDI QIDQ4636659

Could not fetch data.

Publication date: 19 April 2018

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.

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

zbMATH Keywords

Kolmogorov complexityrandomness extractorlist approximation

Mathematics Subject Classification ID

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

Related Items (2)

Towards a nonlinear Schwarz's list ⋮ 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)