# zbMATH — the first resource for mathematics

Extracting Kolmogorov complexity with applications to dimension zero-one laws. (English) Zbl 1223.68060
Bugliesi, Michele (ed.) et al., Automata, languages and programming. 33rd international colloquium, ICALP 2006, Venice, Italy, July 10–14, 2006. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-35904-3/pbk). Lecture Notes in Computer Science 4051, 335-345 (2006).
Summary: 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:
(i) If $$\text{Dim}_{\text{pspace}}(E) > 0$$, then $$\text{Dim}_{\text{pspace}}(E/O(1)) = 1$$.
(ii) $$\text{Dim}(E/O(1)|\text{ESPACE})$$ is either 0 or 1.
(iii) $$\text{Dim}(E/\text{poly} |\text{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 or maximally complex within ESPACE.
For the entire collection see [Zbl 1122.68001].

##### MSC:
 68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: