Limits on the computational power of random strings
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 PR P R and NPR NP R . The two most widely-studied notions of Kolmogorov complexity are the plain complexity C(x) C ( x ) and prefix complexity K(x) K ( x ) ; this gives rise to two common ways to define the set of random strings R : RC R C and RK R K . (Of course, each different choice of universal Turing machine U in the definition of C and K  yields another variant RCU R C U or RKU R K U .) Previous work on the power of R (for any of these variants) has shown: BPP ? { A : A ? tt p R } . PSPACE?PR PSPACE ? P R . NEXP?NPR NEXP ? NP R . Our main contribution is to present the first upper bounds on the complexity of sets that are efficiently reducible to RKU R K U . We show: BPP ? ? 1 0 ? ? U { A : A ? tt p R K U } ? PSPACE . NEXP ? ? 1 0 ? ? U NP R K U ? 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.
kolmogorov complexity prefix complexity uniform derandomization complexity classes