A Kolmogorov Complexity Proof of the Lovasz Local Lemma for Satisfiability

摘要

Recently, Moser and Tardos [MT10] came up with a constructive proof of the Lovasz Local Lemma. In this paper, we give another constructive proof of the lemma, based on Kolmogorov complexity. Actually, we even improve the Local Lemma slightly.