Satisfiability of Almost Disjoint CNF Formulas

Details Satisfiability of Almost Disjoint CNF Formulas Satisfiability of Almost Disjoint CNF Formulas

2008-07-08

arxiv.org/abs/0807.1282v2

Computer Science

Discrete Mathematics

Scientific paper

We call a CNF formula linear if any two clauses have at most one variable in common. Let m(k) be the largest integer m such that any linear k-CNF formula with <= m clauses is satisfiable. We show that 4^k / (4e^2k^3) <= m(k) < ln(2) k^4 4^k. More generally, a (k,d)-CSP is a constraint satisfaction problem in conjunctive normal form where each variable can take on one of d values, and each constraint contains k variables and forbids exacty one of the d^k possible assignments to these variables. Call a (k,d)-CSP l-disjoint if no two distinct constraints have l or more variables in common. Let m_l(k,d) denote the largest integer m such that any l-disjoint (k,d)-CSP with at most m constraints is satisfiable. We show that 1/k (d^k/(ed^(l-1)k))^(1+1/(l-1))<= m_l(k,d) < c (k^2/l ln(d) d^k)^(1+1/(l-1)). for some constant c. This means for constant l, upper and lower bound differ only in a polynomial factor in d and k.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-269074