Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Fundamenta Informaticae Année : 2014

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

Andrei Rumyantsev
  • Fonction : Auteur
Alexander Shen

Résumé

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

Dates et versions

lirmm-01233795 , version 1 (20-04-2019)

Identifiants

Citer

Andrei Rumyantsev, Alexander Shen. Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma. Fundamenta Informaticae, 2014, 132 (1), pp.1-14. ⟨10.3233/FI-2014-1029⟩. ⟨lirmm-01233795⟩
129 Consultations
79 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More