|
Published Articles >> Table of Contents >> Abstract
18th Annual IEEE Conference on Computational Complexity (CCC'03)
p. 135
The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs
Chris Calabro, University of California, San Diego
Russell Impagliazzo
Valentine Kabanets
Ramamohan Paturi
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214416
Send link to a friend
| 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{\delta = / 9 a O\left( {2_{}^{\delta n} } \right)-time randomized algorithm for k-SATg and, similarly, s_k^{} = inf{\delta = 0/ 9 a O(2^{\delta n})-time randomized algorithm for Unique k-SAT}, we show that \lim _k^{} \to \infty S_k^{} =\lim _k^{} \to \infty \delta _k^{} corollary, we prove that, if Unique 3-SAT can be solved in time 2^{en} for every e > 0, then so can k-SAT for all 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 non-trivial, albeit exponentially small, success probability.
|
 Additional Information
|
Citation:
Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi,
"The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs,"
complexity,
p. 135,
18th Annual IEEE Conference on Computational Complexity (CCC'03),
2003
|
|
