MAX-SAT for formulas with constant clause density can be solved faster than in O(2 n ) time

Abstract. We give an exact deterministic algorithm for MAX-SAT. On input CNF formulas with constant clause density (the ratio of the number of clauses to the number of variables is a constant), this algorithm runs in O(c n) time where c < 2 and n is the number of variables. Worst-case upper bounds for MAX-SAT less than O(2 n) were previously known only for k-CNF formulas and for CNF formulas with small clause density.