Extracting Kolmogorov complexity with applications to dimension zero-one laws

Abstract

We apply recent results on extracting randomness from independent sources to ``extract'' Kolmogorov complexity. For any &alpha, &epsilon > 0$, given a string x with K(x) > &alpha|x|, we show how to use a constant number of advice bits to efficiently compute another string y, |y|= &Omega(|x|), with K(y) > (1- &epsilon)|y|. This result holds for both classical and space-bounded Kolmogorov complexity. We use the extraction procedure for space-bounded complexity to establish zero-one laws for polynomial-space strong dimension. Our results include:

If Dim_pspace(E) > 0$, then Dim_pspace(E/O(1)) = 1.
Dim(E/O(1) | ESPACE) is either 0 or 1.
Dim(E/poly | ESPACE) is either 0 or 1.

In other words, from a dimension standpoint and with respect to a small amount of advice, the exponential-time class E is either minimally complex or maximally complex within ESPACE.

33rd International Colloquium on Automata, Languages and Programming, 2006. To appear.