# Complexity of Partial Satisfaction II

### Karl J. Lieberherr

Northeastern University, Boston, USA### Ernst Specker

ETH Zürich, Switzerland

## 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 $τ_{ψ}(0<τ_{ψ}<1)$, 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