Unsatisfiable Linear k-CNFs Exist, for every k
| dc.creator | Scheder, Dominik | |
| dc.date | 2007-08-17 | |
| dc.date.accessioned | 2026-07-07T08:24:06Z | |
| dc.date.available | 2026-07-07T08:24:06Z | |
| dc.description | 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. | |
| dc.description | 11 pages | |
| dc.identifier | https://arxiv.org/abs/0708.2336 | |
| dc.identifier | http://arxiv.org/abs/0708.2336 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/136226 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.title | Unsatisfiable Linear k-CNFs Exist, for every k | |
| dc.type | text |