MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in O(2~n) Time

摘要

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.