Unsatisfiable Linear CNF Formulas Are Large and Complex

Details Unsatisfiable Linear CNF Formulas Are Large and Complex Unsatisfiable Linear CNF Formulas Are Large and Complex

2009-05-11

arxiv.org/abs/0905.1587v5

Computer Science

Discrete Mathematics

12 pages plus a two-page appendix; corrected an inconsistency between title of the paper and title of the arxiv submission

Scientific paper

We call a CNF formula linear if any two clauses have at most one variable in common. We show that there exist unsatisfiable linear k-CNF formulas with at most 4k^2 4^k clauses, and on the other hand, any linear k-CNF formula with at most 4^k/(8e^2k^2) clauses is satisfiable. The upper bound uses probabilistic means, and we have no explicit construction coming even close to it. One reason for this is that unsatisfiable linear formulas exhibit a more complex structure than general (non-linear) formulas: First, any treelike resolution refutation of any unsatisfiable linear k-CNF formula has size at least 2^(2^(k/2-1))$. This implies that small unsatisfiable linear k-CNF formulas are hard instances for Davis-Putnam style splitting algorithms. Second, if we require that the formula F have a strict resolution tree, i.e. every clause of F is used only once in the resolution tree, then we need at least a^a^...^a clauses, where a is approximately 2 and the height of this tower is roughly k.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-701205