The Power of Random Strings

Let R be the set of random strings, the x such that C(x)≥|x|. There are various theorems that many such x must exist at every length. What is the power of R?

R is co-r.e. as one can enumerate small programs to generate the strings x such that C(x)<|x|. One can also reduce the halting problem to R: Suppose we want to know whether a program p halts on blank tape. Let n=|p|. Let t be the number of steps to enumerate all of the strings in R of length 2n. We know when we have enumerated them all by using R. Then if p halts it will halt within t steps. Otherwise let s>t be the number of steps p needs to halt. We can run the enumeration of strings in R of length 2n for s steps. Let x be the lexicographically least string of length 2n not enumerated. We have C(x)≤|p|+O(1) since we need only p to describe this process. But since |p|<2n=|x| this contradicts the fact that we had enumerated all the nonrandom strings.

In this workshop Eric Allender talked about his work with various colleagues looking at what one can get with polynomial-time reductions to random strings. The reduction time above is not bounded by any recursive function. For example they can show any language in PSPACE polynomial-time reduces to R and any language in EXP reduces to R via polynomial-size circuits, as well as many results on different notions of random strings. They use various complexity tools like pseudorandom generators and interactive proof systems in their proofs.