loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
18th Annual IEEE Conference on Computational Complexity (CCC'03)
The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs
Aarhus, Denmark
July 07-July 10
ISBN: 0-7695-1879-6
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.
Citation:
Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi, "The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs," ccc, pp.135, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.