The complexity of Unique k-SAT: An isolation lemma for k-CNFs
Chris Calabro, Russell Impagliazzo, Valentine Kabanets, and Ramamohan Paturi
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, s_{k}= inf {δ≥ 0 | ∃ O(2^{δn})-time randomized algorithm for k-SAT} and, similarly, σ_{k}=inf {δ≥ 0 | ∃ O(2^{δn})-time randomized algorithm for Unique k-SAT}, we show that lim_{k→∞} s_{k}=lim_{k→∞}σ_{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 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 a non-trivial, albeit exponentially small, success probability.
Versions
- journal version in Journal of Computer and System Sciences, 74(3):386-393, 2008.
- extended abstract in Proceedings of the Eighteenth IEEE Conference on Computational Complexity (CCC'03), pages 125-131, 2003.