The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
复制标题
计算复杂性理论中资源有限的柯尔莫哥洛夫复杂性的普遍影响
DOI：
10.1016/j.jcss.2010.06.004
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Sambuddha Roy
中科院分区：
文献类型：
--
作者：
Eric Allender;M. Koucký;Detlef Ronneburger;Sambuddha Roy
我们继续研究资源受限的Kolmogorov复杂性（Allender等人，2006 [4]），它强调了电路复杂性和莱文的时间有界柯尔莫哥洛夫复杂性度量Kt（以及其他具有类似风格的度量）之间的密切联系，并利用去随机化技术提供有关柯尔莫哥洛夫复杂性的新见解。已经引入的Kolmogorov度量与定义资源受限Kolmogorov复杂度的其他方法相比具有许多优点（例如，与用于定义度量的通用机器的底层选择的更大独立性）（Allender等人，2006 [4]）。在这里，我们研究在这个框架中自然产生的其他措施的属性。引入更多的资源受限Kolmogorov复杂性概念的动机是双重的：我们使用这种新的资源受限Kolmogorov复杂性方法提供的主要定理是：
We continue an investigation into resource-bounded Kolmogorov complexity (Allender et al., 2006 [4]), which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity. The Kolmogorov measures that have been introduced have many advantages over other approaches to defining resource-bounded Kolmogorov complexity (such as much greater independence from the underlying choice of universal machine that is used to define the measure) (Allender et al., 2006 [4]). Here, we study the properties of other measures that arise naturally in this framework. The motivation for introducing yet more notions of resource-bounded Kolmogorov complexity are two-fold: The main theorems that we provide using this new approach to resource-bounded Kolmogorov complexity are: