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.
Type de document :
Article dans une revue
Theory of Computing Systems, Springer Verlag, 2011, 9 (2), pp.227-245. 〈http://arxiv.org/abs/0904.3116v4〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736106
Contributeur : Andrei Romashchenko <>
Soumis le : jeudi 27 septembre 2012 - 15:56:43
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 18:18:41

Fichier

csr-journal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. 〈http://arxiv.org/abs/0904.3116v4〉. 〈lirmm-00736106〉

Partager

Métriques

Consultations de la notice

168

Téléchargements de fichiers

208