文章基本信息

标题：List Approximation for Increasing Kolmogorov Complexity
本地全文：下载
作者：Marius Zimand
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：66
页码：58:1-58:12
DOI：10.4230/LIPIcs.STACS.2017.58
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Kolmogorov complexity; list approximation; randomness extractor