×

zbMATH — the first resource for mathematics

Probabilistic constructions of computable objects and a computable version of Lovász local lemma. (English) Zbl 1317.68131
Summary: 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 [the first author, “Infinite computable version of Lovász local lemma”, Preprint, arXiv:1012.0557], we show how the notion of a layerwise computable mapping can be used to prove a computable version of Lovász local lemma.

MSC:
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
03D32 Algorithmic randomness and dimension
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDF BibTeX Cite
Full Text: DOI