A Dichotomy Theorem for Maximum Generalized Satisfiability Problems
A Dichotomy Theorem for Maximum Generalized Satisfiability Problems
复制标题
最大广义可满足性问题的二分定理
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
N. Creignou
中科院分区：
文献类型：
--
作者：
N. Creignou
我们研究了一类无限优化可满足性问题的复杂性。每个问题都通过逻辑关系的有限集合S(推广有界长度的子句的概念)来表示。证明了优化可满足性问题Max-Sat(S)的二分分类的存在性。证明了L的一组特殊的无限逻辑关系：如果S中的每一个关系都是0-有效的(分别为1-有效)，或者如果S中的每一个关系都属于L，那么S的极大可解是多项式时间可解的，否则是极大SNP完全的。因此，ϵ-Sat(S)要么在P中，要么有某种ϵ<的Max-Sat逼近算法；1虽然不是多项式时间逼近格式，但除非P=Np：L={POSN，Negn，Spidern，p，q，Complete-二部，p：n，p，q∈N}，其中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)，和完全二部，p(x1，…，xn，y1，...，yp)≡Λni=1Λpj=1(xi→yj)。
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).