1
$\begingroup$

Roughly speaking, the Kolmogorov Complexity proof of Lovasz local lemma states that for any $k$-CNF $S$ on $n$ variables and $m$ clauses, where the dependency of every clause is bounded by $2^{k-c}$, for some constant $c$, there is a satisfying assignment which can be evaluated in polynomial time.

What is the exact (minimum) value of $c$ for which the lemma holds, and how is this derived?

Thanks in advance.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.