Variations on Muchnik's Conditional Complexity Theorem

Daniil Musatov, Andrei Romashchenko, Alexander Shen

Muchnik's theorem about simple conditional descriptions states that for all strings $a$ and $b$ there exists a short program $p$ transforming $a$ to $b$ that has the least possible…