The Local Lemma Is Tight for SAT

Details The Local Lemma Is Tight for SAT The Local Lemma Is Tight for SAT

2010-06-03

arxiv.org/abs/1006.0744v1

Mathematics

Combinatorics

12 pages

Scientific paper

For every \epsilon > 0 and large enough k we construct unsatisfiable k-CNF formulas where every clause has k distinct literals and every variable appears in at most (2/e +\epsilon)2^k/k clauses. Using a result of Berman, Karpinski and Scott we also show that our result is asymptotically best possible: every k-CNF formula where every variable appears in at most 2^{k+1}/(ek)-1 clauses is satisfiable. The determination of this extremal function is particularly important as it represents the value where the k-SAT problem exhibits its complexity hardness jump: from having every instance being a YES-instance it becomes NP-hard just by allowing each variable to occur in one more clause. The asymptotics of other related extremal functions are also determined. Let l(k) denote the maximum number, such that every k-CNF formula with each clause containing k distinct literals and each clause having a common variable with at most l(k) other clauses, is satisfiable. We establish that the bound on l(k) obtained from the local lemma is asymptotically optimal, i.e., l(k)= (e^{-1}+o(1))2^k. The constructed formulas are all in the class MU(1) of minimal unsatisfiable formulas having one more clause than variables and thus they resolve these asymptotic questions within that class as well.

Affiliated with

Also associated with

No associations

Rating

The Local Lemma Is Tight for SAT 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 The Local Lemma Is Tight for SAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Local Lemma Is Tight for SAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-722377