Skip to Main content Skip to Navigation
Journal articles

Variations on Muchnik's Conditional Complexity Theorem

Daniil Musatov 1 Andrei Romashchenko 2 Alexander Shen 2 
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Muchnik's theorem about simple conditional descriptions states that for all strings a and b there exists a 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. Another version of Muchnik's theorem is proven for a resource-bounded variant of Kolmogorov complexity based on Arthur-Merlin protocols.
Document type :
Journal articles
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Andrei Romashchenko Connect in order to contact the contributor
Submitted on : Thursday, September 27, 2012 - 3:56:43 PM
Last modification on : Friday, August 5, 2022 - 3:02:59 PM
Long-term archiving on: : Friday, December 16, 2016 - 6:18:41 PM


Files produced by the author(s)


  • HAL Id : lirmm-00736106, version 1



Daniil Musatov, Andrei Romashchenko, Alexander Shen. Variations on Muchnik's Conditional Complexity Theorem. Theory of Computing Systems, Springer Verlag, 2011, 9 (2), pp.227-245. ⟨lirmm-00736106⟩



Record views


Files downloads