Unsatisfiable CNF Formulas need many Conflicts

Details Unsatisfiable CNF Formulas need many Conflicts Unsatisfiable CNF Formulas need many Conflicts

2008-06-06

arxiv.org/abs/0806.1148v2

Computer Science

Discrete Mathematics

new version; added an upper bound on the number of conflicts

Scientific paper

A pair of clauses in a CNF formula constitutes a conflict if there is a variable that occurs positively in one clause and negatively in the other. A CNF formula without any conflicts is satisfiable. The Lovasz Local Lemma implies that a k-CNF formula is satisfiable if each clause conflicts with at most 2^k/e-1 clauses. It does not, however, give any good bound on how many conflicts an unsatisfiable formula has globally. We show here that every unsatisfiable k-CNF formula requires 2.69^k conflicts and there exist unsatisfiable k-CNF formulas with 3.51^k conflicts.

Affiliated with

Also associated with

No associations

Rating

Unsatisfiable CNF Formulas need many Conflicts 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 Unsatisfiable CNF Formulas need many Conflicts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unsatisfiable CNF Formulas need many Conflicts will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-172578