ECCC-Report TR05-105https://eccc.weizmann.ac.il/report/2005/105Comments and Revisions published for TR05-105en-usMon, 26 Sep 2005 20:02:24 +0300
Paper TR05-105
| Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws |
Lance Fortnow,
John Hitchcock,
A. Pavan,
N. V. Vinodchandran,
Fengming Wang
https://eccc.weizmann.ac.il/report/2005/105We 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$.
Mon, 26 Sep 2005 20:02:24 +0300https://eccc.weizmann.ac.il/report/2005/105