Randomness and Intractability in Kolmogorov Complexity
Randomness and Intractability in Kolmogorov Complexity
复制标题
柯尔莫哥洛夫复杂性中的随机性和难处理性
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
I. Oliveira
中科院分区：
文献类型：
--
作者：
I. Oliveira
我们引入了随机时间有界Kolmogorov复杂度（rKt），这是Levin的Kolmogorov复杂度概念的自然扩展[24]。低rKt复杂度的字符串w可以通过时间有界算法从短表示中解压缩，该算法以高概率输出w。这个复杂性度量产生了一个关于字符串的决策问题：MrKtP（最小rKt问题）。我们探索的想法，从伪随机证明MrKtP和它的变种不能解决随机准多项式时间。这展示了一个自然的字符串压缩问题，即使是随机计算，也可以证明是棘手的。我们的技术还意味着，没有n1−ε-近似算法MrKtP运行在随机准多项式时间。补充这个下限，我们观察rKt之间的连接，在计算中的随机性的力量，和电路的复杂性。特别是，我们提出了第一个硬度放大定理的自然问题，是无条件的硬对一个强大的计算模型。2012年ACM学科分类计算理论
We introduce randomized time-bounded Kolmogorov complexity (rKt), a natural extension of Levin’s notion [24] of Kolmogorov complexity. A string w of low rKt complexity can be decompressed from a short representation via a time-bounded algorithm that outputs w with high probability. This complexity measure gives rise to a decision problem over strings: MrKtP (The Minimum rKt Problem). We explore ideas from pseudorandomness to prove that MrKtP and its variants cannot be solved in randomized quasi-polynomial time. This exhibits a natural string compression problem that is provably intractable, even for randomized computations. Our techniques also imply that there is no n1−ε-approximate algorithm for MrKtP running in randomized quasi-polynomial time. Complementing this lower bound, we observe connections between rKt, the power of randomness in computing, and circuit complexity. In particular, we present the first hardness magnification theorem for a natural problem that is unconditionally hard against a strong model of computation. 2012 ACM Subject Classification Theory of computation