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 PRPR and NPRNPR.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  ”: RCRC and RKRK. (Of course, each different choice of universal Turing machine U in the definition of C and K   yields another variant RCURCU or RKURKU.) Previous work on the power of “R” (for any of these variants) has shown:•BPP⊆{A:A⩽ttpR}.•PSPACE⊆PRPSPACE⊆PR.•NEXP⊆NPRNEXP⊆NPR. Since these inclusions hold irrespective of low-level details of how “R  ” is defined, and since BPP,PSPACEBPP,PSPACE and NEXP are all in Δ10 (the class of decidable languages), we have, e.g.: NEXP⊆Δ10∩⋂UNPRKU.Our main contribution is to present the first upper bounds on the complexity of sets that are efficiently reducible to RKURKU. We show:•BPP⊆Δ10∩⋂U{A:A⩽ttpRKU}⊆PSPACE.•NEXP⊆Δ10∩⋂UNPRKU⊆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.