A Complexity Index for Satisfiability Problems
Endre Boros, Yves Crama, Peter L. Hammer, Michael Saks · SIAM Journal on Computing · 1994
This paper associates a linear programming problem (LP) to any conjunctive normal form $\phi $, and shows that the optimum value $Z(\phi )$ of this LP measures the complexity of the corresponding ${\textit{SAT}}$ (Boolean satisfiability) problem. More precisely, there is an algorithm for ${\textit{SAT}}$ that runs in polynomial time on the class of satisfiability problems satisfying $Z(\phi ) \leqslant 1 + \tfrac{{c\log n}}{n}$ for a fixed constant c, where c is the number of variables. In contrast, for any fixed $\beta < 1$, $SAT$ is still NP complete when restricted to the class of CNFs for which $Z(\phi ) \leqslant 1 + ({1 / {n^\beta }})$.