A COMPLEXITY INDEX FOR SATISFIABILITY PROBLEMS

This paper associates a linear programming problem (LP) to any conjunc tive normal form phi, and shows that the optimum value Z(phi) of this LP measures the complexity of the corresponding SAT (Boolean satisfiab ility) problem. More precisely, there is an algorithm for SAT that run s in polynomial time on the class of satisfiability problems satisfyin g Z(phi) less-than-or-equal-to 1 + c log n/n for a fixed constant c, w here n 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 wh ich Z(phi) less-than-or-equal-to 1 + (1/n(beta)).