Abstract: What is easy and when does it become hard to find a solution to a problem. We give a sharp answer to this question for various generalizations of the well-known maximum satisfiability problem. For several maximum S-satisfiability problems we explicitly determine algebraic numbers t[S] (t[S] between zero and one), which separate NP-complete from polynomial problems. The fraction t[S] (called a P-optimal threshold) of the clauses of a S-formula can be satisfied in polynomial time, while the set of S-formulas which have an assignment satisfying the fraction t' (t' greater than t[S], t' rational) of the clauses is NP-complete.
The paper is available on the web: Partial Satisfaction II
Highlight of the paper: Theorem 4.1: Let F(p,q) be the class of propositional formulas in conjunctive normal form which contain in each clause at least p positive or at least q negative literals. Let alpha be the solution of (1-x)**p = x**q in (0,1) and let t[p,q] = 1-alpha**q. t[p,q] is the P-optimal threshold for F(p,q).
The proof proceeds through several reduction steps and is non-trivial.
Professor Karl J. Lieberherr College of Computer Science, Northeastern University Avenue of the Arts Boston, MA 02115-9959 Phone: (617) 373 2077 / Fax: (617) 373 5121