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

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