LIPIcs.STACS.2017.58.pdf
- Filesize: 465 kB
- 12 pages
Document
List Approximation for Increasing Kolmogorov Complexity
Author
-
Part of:
Volume:
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-03-06
Cite AsGet BibTex
Marius Zimand. List Approximation for Increasing Kolmogorov Complexity. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 58:1-58:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.58
https://doi.org/10.4230/LIPIcs.STACS.2017.58
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. We obtain similar results for other parameters, including a polynomial-time construction.
Keywords
- Kolmogorov complexity
- list approximation
- randomness extractor
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads