Complexity of Partial Satisfaction II

Abstract

What is easy and when does it become hard to find a solution of a problem? We give a sharp answer to this question for various generalizations of the well-known maximum satisfiability problem. For several maximum $\psi$-satisfiability problems we explicitly determine algebraic numbers ${\tau }_{\psi }(0<{\tau }_{\psi }<1)$, which separate NP-complete from polynomial problems. The fraction ${\tau }_{\psi }$ of the clauses of a $\psi$-formula can be satisfied in polynomial time, while the set of ψ-formulas which have an assignment satisfying the fraction ${\tau }^{\prime }$ $({\tau }^{\prime }>{\tau }_{\psi },{\tau }^{\prime }$  rational) of the clauses is NP-complete.