Name
Abstract | ||
|---|---|---|
We provide some evidence that unique k-SAT is as hard to solve as general k-SAT, where k-SAT denotes the satisfiability problem for k-CNFs and unique k-SAT is the promise version where the given formula has 0 or 1 solutions. Namely, defining for each k≥1, sk=inf{δ≥0|∃aO(2δn)-time randomized algorithm for k-SAT} and, similarly, σk=inf{δ≥0|∃aO(2δn)-time randomized algorithm for Unique k-SAT}, we show that limk→∞sk=limk→∞σk. As a corollary, we prove that, if Unique 3-SAT can be solved in time 2εn for every ε>0, then so can k-SAT for k≥3. Our main technical result is an isolation lemma for k-CNFs, which shows that a given satisfiable k-CNF can be efficiently probabilistically reduced to a uniquely satisfiable k-CNF, with nontrivial, albeit exponentially small, success probability. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1109/CCC.2003.1214416 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
satisfiable k-cnf,satisfiable k-sat complexity,general k-sat,isolation lemma,main technical result,time randomized algorithm,randomised algorithms,k-sat denotes,success probability,search problems,k literal,unique k-sat solvability,computational complexity,computability,algorithm fork-sat,unique k-sat,search problem,unique 3-sat,satisfiability problem,probability,satisfiability,randomized algorithm,polynomials | Conference | 74 |
Issue | ISSN | ISBN |
3 | 1093-0159 | 0-7695-1879-6 |
Citations | PageRank | References |
28 | 1.39 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chris Calabro | 1 | 140 | 6.13 |
| Russell Impagliazzo | 2 | 5444 | 482.13 |
| Valentine Kabanets | 3 | 562 | 35.38 |
| Ramamohan Paturi | 4 | 1260 | 92.20 |