# 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