2-CNF SAT如何在P中，而3-CNF SAT在鼻咽癌中？

Question

我真的很困惑为什么2-CNF SAT在P中，而3-CNF SAT在鼻咽癌中。我读过CLRS，我理解他们是如何证明3-CNF SAT在鼻咽癌的。我不能使用从SAT到2-CNF-SAT的相同还原性来证明2-CNF-SAT在鼻咽癌中是存在的吗？我不明白为什么2-CNF SAT在P中。

Answer 1

为什么2-CNF SAT在P中

因为有一个多项式算法可以解决这个问题。

一个证明的粗略草图：

请注意，2-CNF中的任何子句的格式都是A => B，其中A和B要么是变量，要么是它们的反。因此，我们可以看出，这个子句说当A为真时，它迫使B为真。这也意味着B是假的迫使A为假。我们必须在以后考虑这一点。

现在，您可以一个接一个地获取变量，并搜索它是否传递地强制自身为负(A => B => C => ... => non A)，反之亦然(non A => ... => A)。如果第一个为真，则A必然为假；如果第二个为真，则A为真。如果两者都有，则公式是不可满足的。

如果您没有找到任何使公式不可满足的变量，则它是可满足的。

请注意，这个“粗糙”算法并不是使用图的强连接组件的实际算法，我建议您继续阅读。然而，它是多项式的(对一个变量的搜索显然是O(N^2)，因为考虑到O(N)个子句和O(N)个变量，一次强制一个变量，这意味着算法是多项式的)。请注意，一个子句中最多有两个字面量的事实是至关重要的。如果子句是A => B or C之类的，它就不会工作得那么好。

Answer 2

从CNF SAT到3-CNF SAT的规范缩减是采用像lit_1或lit_2或...或lit_n，并将其替换为两个子句lit_1或lit_2或...或者lit_{floor(n/2)}或者var，lit_{floor(n/2) + 1}或者...或lit_n或NOT var。如果您尝试以这种方式破解一个包含三个字面量的子句，您将得到另一个包含三个字面量的子句，因此相同的证明将不适用于2-CNF SAT (这可能是有充分理由的)。