The complexity of unique k-SAT: An Isolation Lemma for k-CNFs
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 with at most k literals in each clause and Unique k-SAT is the promise version where the given formula has 0 or 1 solutions. Namely, defining for each k >= 1, s(k) = inf{delta >= 0 vertical bar there exists a O(2(delta n))-time randomized algorithm for k-SAT} and, similarly. sigma(k) = inf{delta >= 0 vertical bar there exists a O(2(delta n))-time randomized algorithm for Unique k-SAT}, we show that lim(k ->infinity) s(k) = lim(k ->infinity)sigma(k). a corollary, we prove that, if Unique 3-SAT can be solved in time 2(epsilon n) for every epsilon > 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. (c) 2007 Elsevier Inc. All rights reserved.
k-sat isolation lemma satisfiability unique satisfiability subexponential time reduction