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

• Autorzy: Rumyantsev A. , Shen A.

Identyfikatory

DOI

10.3233/FI-2014-1029

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

probability theory; mathematical proofs; existence theorems; stochastic processes; infinity; mappings

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 132, nr 1
• Strony: 1--14
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Rumyantsev A.

• LIRMM - Laboratoire Informatique Robotique Micro´electronique Montpellier CNRS and Universit´e Montpellier 2, France

autor

Shen A.

• LIRMM - Laboratoire Informatique Robotique Micro´electronique Montpellier CNRS and Universit´e Montpellier 2, France

Bibliografia

• [1] Erdös P., Lovász L., Problems and results of 3-chromatic hypergraphs and some related questions. In: A. Hajnal, R. Rado, V. T. Sós, Eds. Infinite and Finite Sets. North-Holland, II, 609–627.
• [2] Hoyrup M., Rojas C., Applications of Effective Probability Theory to Martin-Löf Randomness. Lectures Notes in Computer Science, 2009, v. 5555, p. 549–561.
• [3] Miller J., Two notes on subshifts. Available from http://www.math.wisc.edu/ jmiller/downloads.html
• [4] Moser R. A., Tardos G., A constructive proof of the general Lovász Local Lemma, Journal of the ACM, 2010, 57(2), 11.1–11.15. See also: http://arxiv.org/abs/0903.0544.
• [5] Rumyantsev A., Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences, STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23–25, 2006. Lecture Notes in Computer Science, 3884, Springer, 2006, p. 396–407.
• [6] Rumyantsev A., Kolmogorov Complexity, Lovász Local Lemma and Critical Exponents. Computer Science in Russia, 2007, Lecture Notes in Computer Science, 4649, Springer, 2007, p. 349-355.
• [7] Rumyantsev A., Everywhere complex sequences and probabilistic method, arxiv.org/abs/1009.3649
• [8] Rumyantsev A., Infinite computable version of Lovasz Local Lemma, arxiv.org/abs/1012.0557
• [9] Zvonkin A. K., Levin L. A., The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Uspekhi Matematicheskikh Nauk, 1970, v. 25, no. 6 (156), p. 85–127.