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: \begin{enumerate}[\upshape (i)] \item If $\Dimpspace(\E) > 0$, then $\Dimpspace(\E/O(1)) = 1$. \item $\Dim(\E/O(1) \mid \ESPACE)$ is either 0 or 1. \item $\Dim(\E/\poly \mid \ESPACE)$ is either 0 or 1. \end{enumerate} 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$.