Linear List-Approximation for Short Programs (or the Power of a Few Random Bits)
Linear List-Approximation for Short Programs (or the Power of a Few Random Bits)
复制标题
短程序的线性列表逼近（或几个随机位的幂）
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Marius Zimand
中科院分区：
文献类型：
--
作者：
Bruno Bauwens;Marius Zimand
字符串x的C -short程序是长度最多为C(x) + C的x的描述，其中C(x)是x的Kolmogorov复杂度。我们展示了存在一种随机算法，该算法构建了包含n个元素的列表，其中包含x的O(log n)-短程序。我们还展示了一个多项式时间随机结构，该结构可为O(log2 n)-短程序实现相同的列表大小。这些结果击败了Bauwens等人在这种列表的确定性构造中所显示的下界。我们还证明了结果的主要参数的紧下界。该结构仅使用O(log n) （O（log2n）用于多项式时间结果）随机位。因此，只要使用少量随机比特，就有可能完成任何确定性算法都无法完成的任务，而不管其运行时间如何。
A c-short program for a string x is a description of x of length at most C(x) + c, where C(x) is the Kolmogorov complexity of x. We show that there exists a randomized algorithm that constructs a list of n elements that contains a O(log n)-short program for x. We also show a polynomial-time randomized construction that achieves the same list size for O(log2 n)-short programs. These results beat the lower bounds shown by Bauwens et al. [1] for deterministic constructions of such lists. We also prove tight lower bounds for the main parameters of our result. The constructions use only O(log n) (O(log2 n) for the polynomial-time result) random bits. Thus using only few random bits it is possible to do tasks that cannot be done by any deterministic algorithm regardless of its running time.