Unsatisfiable Linear k-CNFs Exist, for every k

Details Unsatisfiable Linear k-CNFs Exist, for every k Unsatisfiable Linear k-CNFs Exist, for every k

2007-08-17

arxiv.org/abs/0708.2336v1

Computer Science

Discrete Mathematics

11 pages

Scientific paper

We call a CNF formula linear if any two clauses have at most one variable in common. Let Linear k-SAT be the problem of deciding whether a given linear k-CNF formula is satisfiable. Here, a k-CNF formula is a CNF formula in which every clause has size exactly k. It was known that for k >= 3, Linear k-SAT is NP-complete if and only if an unsatisfiable linear k-CNF formula exists, and that they do exist for k >= 4. We prove that unsatisfiable linear k-CNF formulas exist for every k. Let f(k) be the minimum number of clauses in an unsatisfiable linear k-CNF formula. We show that f(k) is Omega(k2^k) and O(4^k*k^4), i.e., minimum size unsatisfiable linear k-CNF formulas are significantly larger than minimum size unsatisfiable k-CNF formulas. Finally, we prove that, surprisingly, linear k-CNF formulas do not allow for a larger fraction of clauses to be satisfied than general k-CNF formulas.

Affiliated with

Also associated with

No associations

Rating

Unsatisfiable Linear k-CNFs Exist, for every k 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 k-CNFs Exist, for every k, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unsatisfiable Linear k-CNFs Exist, for every k will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-5832