Finding almost-satisfying assignments
Finding almost-satisfying assignments
复制标题
找到几乎令人满意的作业
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Uri Zwick
中科院分区：
文献类型：
--
作者：
Uri Zwick
Schaefer很久以前就证明了，本质上只有三类合取布尔公式(或约束满足问题)可以在多项式时间(假设P$NP)内判定可满足性，这三类是LIN、2-SAT和Horn-SAT。LIN是所有约束都是线性方程的约束满足问题，模2-SAT是所有约束至多是两个变量的析取或它们的否定的约束满足问题。Horn-SAT是一个约束满足问题，其中所有的约束都是Horn子句，即至多包含一个否定变量的析取。给出令人满意的LIN、P-SAT和HORNSAT的例子，我们可以非常有效地找到满意的任务。然而，假设我们所给出的实例只是几乎可满足的，即，对于一些小的Conant e>；0，存在满足其1e约束的赋值，但没有满足其所有约束的赋值。我们能否有效地找到几乎令人满意的分配，即满足1个f(E)约束的分配，其中f(C)是趋于0而E趋于01的函数，对于LIN，答案是‘否’。H&ad证明了，对于任一e>；0和6>；0，找到满足LIN的(1e)-可满足实例的约束的L/2-t6的指派是NP难的。与此形成鲜明对比的是，我们在这里展示了2SAT和Horn-SAT的答案是‘是’。给定P-SAT和Horn-SAT的几乎满意的实例，我们可以迅速地找到几乎满意的赋值。更具体地说，给定一个(1e)-可满足的2-SAT公式，我们可以迅速地找到一个(10(E_1/3))-满足的分配。给出一个(1-c)-可满足的Horn-Sat公式，我们可以从计算机科学学院计算机科学学院，以色列特拉维夫69978，IBL Aviv大学雷蒙德和贝弗利·萨克勒精确科学学院。电子邮件：zuickdYnath.tau.ac.il。有效地找到一个满足(10(loglog$/log$))的任务。我们的结果，再加上Khanna、苏丹和Williamson得到的Schaefer结果的推广，表明ZSAT和Horn-SAT本质上是仅有的在多项式时间内(假设P#NP)可以找到几乎满意的赋值的非平凡公式类。
Schaefer showed, long ago, that there are, essentially, only three non-trivial classes of conjunctive Boolean formulae (or constraint satisfaction problems) for which oatisflability can be decided in polynomial time (assuming P $ NP), These three classes are LIN, 2-SAT and HORN-SAT. LIN is the constraint satisfaction problem in which all the constraints are linear equations modulo 2, 2-SAT is the constraint satisfaction problem in which all the constraints are disjunctions of at most two variables or their negations. HORN-SAT is the constraint satisfaction problem in which all the constraints are Horn clauses, i.e., disjunctions containing at most one negated variable. Given aatisfiable instances of LIN, P-SAT and HORNSAT, we can very efficiently find satisfying assignments. Suppose, however, that the instances that we are given are only almost-satisfiable, i.e., there are assignments that satisfy 1 e of their constraints, for some small con&ant e > 0, but no assignments that satisfy all their constraints. Can we efficiently find almost-satisfying assignments, i.e., assignments that satisfy 1 f(e) of the constraints, where f(c) is a function that tends to 0 an E tends to 01 For LIN, the answer turns out to be ‘no’. H&ad showed that, for any e > 0 and 6 > 0, finding an assignment hat satisfies l/2 -t 6 of the constraints of a (1 e)-satisfiable instance of LIN is NP-hard. In sharp contrast, we show here that the answer for 2SAT and HORN-SAT is ‘yes’. Given almost-satisfiable instances of P-SAT and of HORN-SAT we cun efhcicntly find almost-satisfying assignments. More specifically, given a (1 e)-satisfiable 2-SAT formula we can eflicicntly find a (1 O(e1/3))-satisfying assignment. Given a (1-c)-satisfiable HORN-SAT formula we can ‘Dopnrtment of Computer Science, School of Mathematical Bclenceo, Raymond and Beverly Sackler Faculty of Exact Scioncen, ‘Ibl Aviv University, Tel Aviv 69978, ISRAEL. Email: zuickdYnath.tau.ac.il. efficiently find a (1 O(loglog $/log $))-satisfying assignment. Our results, combined with extensions of Schaefer’s results obtained by Creignou and by Khanna, Sudan and Williamson, imply that ZSAT and HORN-SAT are, essentially, the only non-trivial classes of formulae for which almost-satisfying assignments can be found in polynomial time (assuming P # NP).