  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 length and is simple conditional on $b$. In this
paper we present two new proofs of this theorem. The first one is based on the
on-line matching algorithm for bipartite graphs. The second one, based on
extractors, can be generalized to prove a version of Muchnik's theorem for
space-bounded Kolmogorov complexity.
