JournalsemVol. 67, No. 3pp. 134–150

Complexity of Partial Satisfaction II

  • Karl J. Lieberherr

    Northeastern University, Boston, USA
  • Ernst Specker

    ETH Zürich, Switzerland
Complexity of Partial Satisfaction II cover
Download PDF

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)τ_ψ (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