Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-105 | 24th September 2005 00:00

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws


Authors: Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang
Publication: 26th September 2005 20:02
Downloads: 3206


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.
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$.

ISSN 1433-8092 | Imprint