\input zb-basic
\input zb-ioport
\iteman{io-port 06110689}
\itemau{Messner, Jochen; Thierauf, Thomas}
\itemti{A Kolmogorov complexity proof of the Lov\'asz local lemma for satisfiability.}
\itemso{Theor. Comput. Sci. 461, 55-64 (2012).}
\itemab
Summary: The Lov\'asz Local Lemma provides a syntactic property that a Boolean formula is satisifiable. Moser and Tardos came up with a constructive proof of the lemma, i.e. the proof gives a method to actually construct a satisfying assignment. In this paper, we give another constructive proof of the lemma, based on Kolmogorov complexity. Actually, we even improve their result slightly.
\itemrv{~}
\itemcc{}
\itemut{Lov\'asz local lemma; satisfiability; Kolmogorov complexity}
\itemli{doi:10.1016/j.tcs.2012.06.005}
\end