Complexity of Partial Satisfaction II
Karl J. Lieberherr
Northeastern University, Boston, USAErnst Specker
ETH Zürich, Switzerland
![Complexity of Partial Satisfaction II cover](/_next/image?url=https%3A%2F%2Fcontent.ems.press%2Fassets%2Fpublic%2Fimages%2Fserial-issues%2Fcover-em-volume-67-issue-3.png&w=3840&q=90)
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 -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