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

Issue title: Russian-Finnish Symposium in Discrete Mathematics

Article type: Research Article

Authors: Rumyantsev, Andrei | Shen, Alexander

Affiliations: LIRMM - Laboratoire Informatique Robotique Microélectronique Montpellier CNRS and Université Montpellier 2, France. [email protected], [email protected]

Note: [] Address for correspondence: LIRMM CNRS & UM 2, Montpellier, France; on leave from IITP RAS, Moscow. Supported by ANR NAFIT-008-01/2 grant add also the EMC ANR-09-BLAN-0164 grant.

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ász local lemma.

DOI: 10.3233/FI-2014-1029

Journal: Fundamenta Informaticae, vol. 132, no. 1, pp. 1-14, 2014