Families of unsatisfiable k-CNF formulas with few occurrences per variable
| dc.creator | Hoory, Shlomo | |
| dc.creator | Szeider, Stefan | |
| dc.date | 2004-11-08 | |
| dc.date.accessioned | 2026-07-07T05:14:05Z | |
| dc.date.available | 2026-07-07T05:14:05Z | |
| dc.description | (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. | |
| dc.identifier | https://arxiv.org/abs/math/0411167 | |
| dc.identifier | http://arxiv.org/abs/math/0411167 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/73144 | |
| dc.subject | Combinatorics | |
| dc.title | Families of unsatisfiable k-CNF formulas with few occurrences per variable | |
| dc.type | text |