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\geq 1$, $s_k=\inf\{\delta\geq 0\mid \exists\text{ a $O(2^{\delta n})$-time randomized}$ $\text{algorithm for $k$-SAT}\}$ and, similarly, $\sigma_k=\inf\{\delta\geq 0\mid$ $\exists\text{ a $O(2^{\delta n})$-time randomized algorithm for Unique}$ $\text{$k$-SAT}\}$, we show that $\lim_{k\to\infty}s_k=\lim_{k\to\infty}\sigma_k$. As 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\geq 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.

Versions