Variations on Muchnik's Conditional Complexity Theorem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Theory of Computing Systems Année : 2011

Variations on Muchnik's Conditional Complexity Theorem

Résumé

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.
Fichier principal
Vignette du fichier
csr-journal.pdf (224.51 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00736106 , version 1 (27-09-2012)

Identifiants

Citer

Daniil Musatov, Andrei Romashchenko, Alexander Shen. Variations on Muchnik's Conditional Complexity Theorem. Theory of Computing Systems, 2011, 9 (2), pp.227-245. ⟨10.1007/s00224-011-9321-z⟩. ⟨lirmm-00736106⟩
118 Consultations
258 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More