A Duality between Clause Width and Clause Density for SAT

Abstract

We consider the relationship between the complexities of k-SAT and those of SAT restricted to formulas of constant density. Let s <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k </sub> be the infimum of those c ges 0 such that k-SAT on n variables can be decided in time O(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">cn</sup> ) and d <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Delta</sub> be the infimum of those c ges 0 such that SAT on n variables and les Deltan clauses can be decided in time O(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">cn</sup> ). We show that lim <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">krarrinfin</sub> s <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> = lim <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Deltararrinfin</sub> d <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Delta</sub> . So, for any epsi > 0, k-SAT can be solved in 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(1-epsi)n</sup> time independent of k if and only if the same is true for SAT with any fixed density of clauses to variables. We derive some interesting consequences from this. For example, assuming that 3-SAT is exponentially hard (that is, s <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sub> > 0), SAT of any fixed density can be solved in time whose exponent is strictly less than that for general SAT. We also give an improvement to the sparsification lemma of Impagliazzo et al. (1998) showing that instances of k-SAT of density slightly more than exponential in k are almost the hardest instances of k-SAT. The previous result showed this for densities doubly exponential in k