Randomness is hard
Randomness is hard
复制标题
随机性很难
DOI：
10.1109/ccc.1998.694616
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
L. Torenvliet
中科院分区：
文献类型：
--
作者：
H. Buhrman;L. Torenvliet
我们研究了Kolmogorov复杂性的各种资源受限形式的不可压缩字符串集。我们研究的Kolmogorov复杂性的资源有界版本有：Sipser定义的多项式时间CD复杂性，Buhrman和Fortnow定义的不确定变量，以及Hartmanis引入的多项式空间有界Kolmogorov复杂性CS。对于所有这些度量，我们将随机串集合R/SUPT//SUP CD/、R/SUB T//SUP CND/和R/SUB S//SUP CS/定义为使得对于S和t多项式，CD/SUP t/(X)、CND/SUP t/(X)和CS/SUP S/(X)大于或等于x的长度的字符串集合。我们证明了：MA/SPL Sube/NP(R/subt//sup CD/)，其中MA是Babai定义的Merlin-Arthur对策类。AM/SPL Sube/NP(R/subt//sup CND/)，其中AM是Arthur-Merlin对策的类。(/子S//上级CS/)这些结果表明，对于不确定约简下的复杂类，不同资源边界下的随机串集合是困难的。本文对比了Buhrman和Mayordomo的早期工作，他们证明了对于多项式时间确定性约简，指数时间Kolmogorov随机串的集合是不完备的。
We study the set of incompressible strings for various resource bounded versions of Kolmogorov complexity. The resource bounded versions of Kolmogorov complexity we study are: polynomial time CD complexity defined by Sipser, the nondeterministic variant due to Buhrman and Fortnow, and the polynomial space bounded Kolmogorov complexity, CS introduced by Hartmanis. For all of these measures we define the set of random strings R/sub t//sup CD/, R/sub t//sup CND/, and R/sub s//sup CS/ as the set of strings x such that CD/sup t/(x), CND/sup t/(x), and CS/sup s/(x) is greater than or equal to the length of x, for s and t polynomials. We show the following: MA/spl sube/NP(R/sub t//sup CD/), where MA is the class of Merlin-Arthur games defined by Babai. AM/spl sube/NP(R/sub t//sup CND/), where AM is the class of Arthur-Merlin games. PSPACE/spl sube/NP(/sub s//sup CS/). These results show that the set of random strings for various resource bounds is hard for complexity classes under nondeterministic reductions. This paper contrasts the earlier work of Buhrman and Mayordomo where they show that for polynomial time deterministic reductions the set of exponential time Kolmogorov random strings is not complete.