Extractors and an efficient variant of Muchnik's theorem

Abstract

Muchnik's theorem about simple conditional descriprion states that for all words $a$ and $b$ there exists a short program $p$ transforming $a$ to $b$ that has the least possible length and is simple conditional on $b$. This paper presents a new proof of this theorem, based on extractors. Employing the extractor technique, two new versions of Muchnik's theorem for space- and time-bounded Kolmogorov complexity are proven.

37 pages, in Russian