A Fast Deterministic Algorithm for Formulas That Have Many Satisfying Assignments
A Fast Deterministic Algorithm for Formulas That Have Many Satisfying Assignments
复制标题
具有许多令人满意的赋值的公式的快速确定性算法
作者：
E. Hirsch
对于一个有许多满意赋值的布尔公式，我们如何找到满意的赋值呢？存在一个明显的随机算法来解决这个问题：人们可以随机选择一个分配，并检查这个分配的公式的真值，这是迭代，直到出现一个令人满意的分配。是否存在一个多项式时间确定性算法来解决同样的问题？本文提出了这样一个算法，并表明，它的最坏情况下的运行时间是线性的输入公式是在k-CNF和一个分数的满意的分配（在所有可能的分配）是大于一个常数。该算法与Monien和Speckenmeyer（以及Dantsin独立提出的）在80年代早期提出的少于2n步的3-SAT判决算法几乎相同。本文的另一个结果是，如果k-CNF中的公式有许多令人满意的分配，那么存在一个短的令人满意的分配，即真值分配给少数变量。所提出的算法产生这样一个短的满意的分配。我们还表明，存在公式一般CNF有许多满意的任务，没有短的满意的任务。
How can we find any satisfying assignment for a Boolean formula that has many satisfying assignments? There exists an obvious randomized algorithm for solving this problem: one can just pick an assignment at random and check the truth value of the formula for this assignment, this is iterated until a satisfying assignment occurs. Does there exist a polynomial-time deterministic algorithm that solves the same problem? This paper presents such an algorithm and shows that its worst-case running time is linear when input formulas are in k-CNF and a fraction of satisfying assignments (among all possible assignments) is greater than a constant. This algorithm is almost the same as the algorithm proposed by Monien and Speckenmeyer (and independently by Dantsin) in the early 1980s for less than 2n steps 3-SAT decision. Another result of this paper is that if a formula in k-CNF has many satisfying assignments, then there exists a short satisfying assignment, i.e. an assignment of truth values to a small number of variables. The proposed algorithm yields just such a short satisfying assignment. We also show that there exist formulas in general CNF having many satisfying assignments, that have no short satisfying assignments.