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
Journal Articles Fundamenta Informaticae Year : 2014

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

Andrei Rumyantsev
  • Function : Author
Alexander Shen

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.)
Fichier principal
Vignette du fichier
1305.1535.pdf (351.73 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
137 View
86 Download

Altmetric

Share

More