在NP中发现由（DNF形式）分开的2SAT方程系统的解决方案

Question

我想知道是否找到由或门（如下dnf形式）的特定数量的2sat等式的解决方案是p或np。

等式具有总N个变量，每个条款都是2SAT方程在1到N的变量子集中。 示例：

f= [（x1 || x2）&&（！x2 || x3）&&（x3 || x4）] ||[（x2 || x5）&&（x3 || x6）&&（！x4 ||！x6）] ||....

等式F是2SAT方程的DNF，它已经说过M子句。在NP中找到解决方案？如果是如何？

此外，特别是我也想知道查找等式f的假实例是否在p或np中。

Answer 1

• 首先，请注意问题的标题有点误导，因为 $ p $ 是 $的子集np $ 。另见yuval filmus的评论。我假设你想要的是什么，是它是否在 $ p $ 或 $ np \中setminus p $ 。
此外，“DNF”的名称具体是指<强>基本的连词的分离，而不是任意功能的分离。你描述的是dnf，而是cnfs的分离。

用那个方式，这是我的答案。

---

1. 为了满足2-cnfs的分离，您所需要的只是满足它们的<强>一个。因此，如果将2-SAT算法应用于第一个CNFS并获得“是”，那么整个问题的答案是“是”。否则，您只需继续到第二个，等等。不应该花很长时间，因为你只有它们的 m 。如果不能单独满足它们，即它们都是恒定的零，那么显然整个事情是恒定的零。

   所以第一个部分的答案是：问题在p中，具有以下决策算法：

   每2-CNF，应用“正常”2-SAT算法（分辨率规则），以确定它是否满意。如果“是”，只需返回“是”。如果您在没有找到“是”的情况下通过所有这些，则返回“否”。

---

现在，发现该公式的“假”案例（也称为Tautolool的问题）是另一个问题。有一件事，对于摩根的规则，德尔根的规则，of ors of ors的TaItology of ors of ors ands ands的可靠性。但这只是一个已经是一般的SAT问题的更普遍情况，不是吗？

考虑将一组可能的公式限制为每个两个元素分离真正只有一个元素，重复的那些可能会发生什么。所以它是一种配方 $$ f= [（x_1 \ vee x_1）\＆（\ neg x_2 \ vee \ neg x_2）\＆（x_3 \ vee x_3）] \ vee [（x_2 \ vee x_2）\＆（x_4 \ vee x_4）\＆（ x_5 \ vee x_5）] \ vee ... $$ 这相当于 $$ f= [x_1 \＆\ neg x_2 \＆x_3] \ vee [x_2 \＆x_4 \＆x_5] \ vee ... $$ 这只是一个正常的dnf。在摩根转型后，获得正常的CNF，其可靠性是NP-HARD。因此，包含该一个作为子集的任何问题也将至少为np-chally。

显然，有问题的问题不会在 np之外，因为它仍然是多项式可验证的。所以你的第二个问题的答案是“在NP中，但不是在P”中。