Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma

Andrei Rumyantsev Alexander Shen 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A nonconstructive proof can be used to prove the existence of an object with some properties without providing an explicit example of such an object. A special case is a probabilistic proof where we show that an object with required properties appears with some positive probability in some random process. Can we use such arguments to prove the existence of a computable infinite object? Sometimes yes: following [8], we show how the notion of a layerwise computable mapping can be used to prove a computable version of Lov\'asz local lemma. (A survey of Moser-Tardos proof is included to make the paper self-contained.)
Type de document :
Article dans une revue
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2014, 132 (1), pp.1-14. 〈10.3233/FI-2014-1029〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01233795
Contributeur : Alexander Shen <>
Soumis le : mercredi 25 novembre 2015 - 17:49:27
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Lien texte intégral

Identifiants

Collections

Citation

Andrei Rumyantsev, Alexander Shen. Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2014, 132 (1), pp.1-14. 〈10.3233/FI-2014-1029〉. 〈lirmm-01233795〉

Partager

Métriques

Consultations de la notice

87