科研之友
微信
新浪微博
Facebook
分享链接
摘要
How powerful is the set of random strings? What can one say about a set A that is efficiently reducible to R, the set of Kolmogorov-random strings? We present the first upper bound on the class of computable sets in P-R and NPR. The two most widely-studied notions of Kolmogorov complexity are the "plain" complexity C(x) and "prefix" complexity K(x); this gives rise to two common ways to define the set of random strings "R": R-C and R-K. (Of course, each different choice of universal Turing machine U in the definition of C and K yields another variant R-CU or R-KU) Previous work on the power of "R" (for any of these variants) has shown: BPP subset of {A: A <=(p)(tt) R}. PSPACE subset of P-R, NEXP subset of NPR. Since these inclusions hold irrespective of low-level details of how "R" is defined, and since BPP, PSPACE and NEXP are all in Delta(0)(1) (the class of decidable languages), we have, e.g.: NEXP subset of Delta(0)(1) boolean AND boolean AND(U) NPRKU Our main contribution is to present the first upper bounds on the complexity of sets that are efficiently reducible to R-KU. We show: BPP subset of Delta(0)(1) boolean AND boolean AND(U) {A: <=(p)(tt) R-KU} subset of PSPACE. NEXP subset of Delta(0)(1) boolean AND boolean AND(U) NPRKU subset of EXPSPACE. Hence, in particular, PSPACE is sandwiched between the class of sets polynomial-time Turing- and truth-table-reducible to R. As a side-product, we obtain new insight into the limits of techniques for derandomization from uniform hardness assumptions.
- 出版日期2013-1
