Limits on the computational power of random strings

Eric Allender, Luke Friedman, William Gasarch

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


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

Original languageEnglish (US)
Pages (from-to)80-92
Number of pages13
JournalInformation and Computation
StatePublished - Jan 2013

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


  • Complexity classes
  • Kolmogorov complexity
  • Prefix complexity
  • Uniform derandomization


Dive into the research topics of 'Limits on the computational power of random strings'. Together they form a unique fingerprint.

Cite this