Name
Title | ||
|---|---|---|
Uniquely satisfiable k-SAT instances with almost minimal occurrences of each variable |
Abstract | ||
|---|---|---|
Let (k,s)-SAT refer the family of satisfiability problems restricted to CNF formulas with exactly k distinct literals per clause and at most s occurrences of each variable. Kratochvíl, Savický and Tuza [6] show that there exists a function f(k) such that for all s≤f(k), all (k,s)-SAT instances are satisfiable whereas for k≥3 and sf(k), (k,s)-SAT is NP-complete. We define a new function u(k) as the minimum s such that uniquely satisfiable (k,s)-SAT formulas exist. We show that for k≥3, unique solutions and NP-hardness occur at almost the same value of s: f(k)≤u(k)≤f(k)+2. We also give a parsimonious reduction from SAT to (k,s)-SAT for any k≥3 and s≥f(k)+2. When combined with the Valiant–Vazirani Theorem [8], this gives a randomized polynomial time reduction from SAT to UNIQUE-(k,s)-SAT. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-14186-7_34 | SAT |
Keywords | Field | DocType |
satisfiability problem,new function u,unique solution,randomized polynomial time reduction,satisfiable k-sat instance,sat formula,cnf formula,k distinct literal,minimal occurrence,sat instance,parsimonious reduction,vazirani theorem,satisfiability | Discrete mathematics,Combinatorics,Existential quantification,Satisfiability,Conjunctive normal form,Mathematics,Polynomial-time reduction | Conference |
Volume | ISSN | ISBN |
6175 | 0302-9743 | 3-642-14185-4 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| William Matthews | 1 | 8 | 0.84 |
| Ramamohan Paturi | 2 | 1260 | 92.20 |