Families of unsatisfiable k-CNF formulas with few occurrences per variable

Details Families of unsatisfiable k-CNF formulas with few occurrences per variable Families of unsatisfiable k-CNF formulas with few occurrences per variable

2004-11-08

arxiv.org/abs/math/0411167v1

Mathematics

Combinatorics

Scientific paper

(k,s)-SAT is the satisfiability problem restricted to instances where each clause has exactly k literals and every variable occurs at most s times. It is known that there exists a function f such that for s\leq f(k) all (k,s)-SAT instances are satisfiable, but (k,f(k)+1)-SAT is already NP-complete (k\geq 3). The best known lower and upper bounds on f(k) are Omega(2^k/k) and O(2^k/k^a), where a=\log_3 4 - 1 = 0.26.... We prove that f(k) = O(2^k \cdot \log k/k), which is tight up to a \log k factor.

Affiliated with

Also associated with

No associations

Rating

Families of unsatisfiable k-CNF formulas with few occurrences per variable 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 Families of unsatisfiable k-CNF formulas with few occurrences per variable, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Families of unsatisfiable k-CNF formulas with few occurrences per variable will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-109507