Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

Lance Fortnow, John M. Hitchcock, A. Pavan, N. V. Vinodchandran, and Fengming Wang

Abstract:
We apply recent results on extracting randomness from independent sources to "extract" Kolmogorov complexity. For any α, ε > 0, given a string x with K(x) > α|x|, we show how to use a constant number of advice bits to efficiently compute another string y, |y|=Ω(|x|), with K(y) > (1-ε)|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:

  1. If Dimpspace(E) > 0, then Dimpspace(E/O(1)) = 1.
  2. Dim(E/O(1) | ESPACE) is either 0 or 1.
  3. 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 (dimension 0) or maximally complex (dimension 1) within ESPACE.