On Extracting Space-bounded Kolmogorov Complexity

We present two theorems about extracting space-bounded Kolmogorov complexity. Roughly speaking, they say about extracting complexity from two sources and from one source respectively. Their proofs employ the same “naive” derandomization technique: a random construction is replaced by a pseudo-random one obtained by the Nisan-Wigderson generator. Extracting complexity from two sources is done by an analogue of Kolmogorov extractor. It receives two strings with sufficiently large space-bounded Kolmogorov complexities and sufficiently small “dependency”. From these arguments an extractor produces a string with complexity close to the length. An extractor is strong if complexity is still close to the length even conditional to one of the initial strings. We prove that there exist such functions with near optimal parameters. Extracting complexity from one source uses the ideas of Muchnik’s theorem on conditional complexity. We prove that in space-bounded framework any string a has a “universal code” p such that two properties hold. First, p is simple conditional on a. Second, for any string b of polynomial length a is simple conditional on b and the C ^s (a|b)-bit prefix of p. It turns out that this prefix has complexity close to its length, causing the term “extraction”.