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 metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736106
Contributor : Andrei Romashchenko <>
Submitted on : Thursday, September 27, 2012 - 3:56:43 PM
Last modification on : Wednesday, May 13, 2020 - 3:02:09 PM
Long-term archiving on: : Friday, December 16, 2016 - 6:18:41 PM

File

csr-journal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00736106, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

239

Files downloads

417