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

Andrei Rumyantsev, Alexander Shen

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 probabilis…