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 -satisfiability problems we explicitly determine algebraic numbers , which separate NP-complete from polynomial problems. The fraction of the clauses of a -formula can be satisfied in polynomial time, while the set of ψ-formulas which have an assignment satisfying the fraction rational) of the clauses is NP-complete.
Cite this article
Karl J. Lieberherr, Ernst Specker, Complexity of Partial Satisfaction II. Elem. Math. 67 (2012), no. 3, pp. 134–150DOI 10.4171/EM/202