A Dichotomy Theorem for Maximum Generalized Satisfiability Problems

摘要

We study the complexity of an infinite class of optimization satisfiability problems. Each problem is represented through a finite set, S, of logical relations (generalizing the notion of clauses of bounded length). We prove the existence of a dichotomic classification for optimization satisfiability problems Max-Sat(S). We exhibit a particular infinite set of logical relations L, such that the following holds: If every relation in S is 0-valid (respectively 1-valid) or if even/relation in S belongs to L, then Max-Sat(S) is solvable in polynomial time, otherwise it is MAX SNP-complete. Therefore, Max-Sat(S) either is in P or has some ϵ-approximation algorithm with ϵ < 1 although not a polynomial-time approximation scheme, unless P = NP: L = {Posn, Negn, Spidern,p,q, Complete-Bipartiten,p:n, p, q ∈ N}, where Posn(x1, ..., xn) ≡ (x1 ∧ ··· ∧ xn),Negn(x1, ..., xn) ≡ (¬x1 ∧ ··· ∧ ¬xn),Spider n,p,q(x1, ..., xn, y1, ..., yp, z1 ..., zq) ≡ Λni=1 (xi → y1) ∧ Λpi=1 (y1≡yi ∧ Λqi=1 (y1 → zi), andComplete-Bipartiten,p(x1, ..., xn, y1, ..., yp) ≡ Λni=1 Λpj=1 (xi → yj).