Skip to Main content Skip to Navigation
Journal articles

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.)
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01233795
Contributor : Alexander Shen <>
Submitted on : Saturday, April 20, 2019 - 10:53:51 AM
Last modification on : Saturday, April 20, 2019 - 11:25:40 AM

File

1305.1535.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

209

Files downloads

84