Infinite computable version of Lovasz Local Lemma

Details Infinite computable version of Lovasz Local Lemma Infinite computable version of Lovasz Local Lemma

2010-12-02

arxiv.org/abs/1012.0557v1

Computer Science

Data Structures and Algorithms

Scientific paper

Lov\'asz Local Lemma (LLL) is a probabilistic tool that allows us to prove the existence of combinatorial objects in the cases when standard probabilistic argument does not work (there are many partly independent conditions). LLL can be also used to prove the consistency of an infinite set of conditions, using standard compactness argument (if an infinite set of conditions is inconsistent, then some finite part of it is inconsistent, too, which contradicts LLL). In this way we show that objects satisfying all the conditions do exist (though the probability of this event equals~$0$). However, if we are interested in finding a computable solution that satisfies all the constraints, compactness arguments do not work anymore. Moser and Tardos recently gave a nice constructive proof of LLL. Lance Fortnow asked whether one can apply Moser--Tardos technique to prove the existence of a computable solution. We show that this is indeed possible (under almost the same conditions as used in the non-constructive version).

Affiliated with

Also associated with

No associations

Rating

Infinite computable version of Lovasz Local Lemma does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Infinite computable version of Lovasz Local Lemma, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Infinite computable version of Lovasz Local Lemma will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-512911