## Abstract

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 NP^{R}. 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 or R_{KU}.) Previous work on the power of "R" (for any of these variants) has shown:BPP⊆{A:A≤_{tt}^{p}R}. PSPACE⊆P^{R}.NEXP⊆NP^{R}. Since these inclusions hold irrespective of low-level details of how "R" is defined, and since BPP,PSPACE and NEXP are all in Δ_{1}^{0} (the class of decidable languages), we have, e.g.: NEXP⊆Δ_{1} ^{0}∩∩_{U}NP^{RKU}. 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⊆Δ_{1} ^{0}∩∩_{U}{A:A≤_{tt}pR_{KU}} ⊆PSPACE.NEXP⊆Δ_{1}^{0}∩∩ _{U}NP^{RKU}⊆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 language | English (US) |
---|---|

Pages (from-to) | 80-92 |

Number of pages | 13 |

Journal | Information and Computation |

Volume | 222 |

DOIs | |

State | Published - Jan 2013 |

## All Science Journal Classification (ASJC) codes

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

## Keywords

- Complexity classes
- Kolmogorov complexity
- Prefix complexity
- Uniform derandomization