Résumé
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 oil b. In this paper We present two new proofs of this theorem. The first one is based oil the on-line matching algorithm for bipartite graphs. The second one, based on extractors, call be generalized to prove a version of Muchnik's theorem for space-bounded Kolmogorov complexity.