Complexity of Partial Satisfaction

Abstract

A conjunctive-normal-form expression (cnf) IS said to be 2-satisfiable if and only if any two of its clauses are simultaneously satisfiable It is shown that every 2-satisfiable cnf has a truth assignment that satisfies at least the fraction h of its clauses, where h = (x/5 -1)/2 ~ 0.618 (the reciprocal of the "golden ratio"). The proof ~s constructive m that it provides a polynomtal-ume algorithm that will find for any 2-sausfiable cnf a truth assignment satisfying at least the fraction h of its clauses. Furthermore, this result is optimal m that the constant h IS as large as possible. It is shown that, for any rational h' > h, the set of all 2-satisfiable cnfs that have truth assignments satisfying at least the fraction h' of their clauses ~s an NP-complete set gEY WORDS AND PHRASES doubly transltwe permutations, golden mean, NP-complete, polynomial enumeration algorithm, polynomially constructive reductions, satlsfiabdlty CR CATEGORIES 5.21, 5.25,