TR05-105 Authors: Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang

Publication: 26th September 2005 20:02

Downloads: 3159

Keywords:

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