Complexity of partial satisfaction. II. (Q452481)

Summary: 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 \(\psi\)-satisfiability problems we explicitly determine algebraic numbers \(\tau_{\psi}\), \(0<\tau_{\psi} < 1\), which separate NP-complete from polynomial problems. The fraction \(\tau_{\psi}\) of the clauses of a \(\psi\)-formula can be satisfied in polynomial time, while the set of \(\psi\)-formulas which have an assignment satisfying the fraction \(\tau'\), where \(\tau' > \tau_{\psi}\) and \(\tau'\) is rational, of the clauses is NP-complete. For Part I see [the authors, J. Assoc. Comput. Mach. 28, 411--421 (1981; Zbl 0456.68078)].