Complexity of Partial Satisfaction II

  • Karl J. Lieberherr

    Northeastern University, Boston, USA
  • Ernst Specker

    ETH Zürich, Switzerland


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–150

DOI 10.4171/EM/202