Extractors and an efficient variant of Muchnik's theorem

Daniil Musatov

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 le…