algorithm - 2-CNF SAT如何在P中，而3-CNF SAT在NPC中？

Question

我真的很困惑为什么 2-CNF SAT 在 P 中，而 3-CNF SAT 在 NPC 中。我读过 CLRS，我了解他们如何证明 3-CNF SAT 在 NPC 中。我不能使用从 SAT 到 2-CNF-SAT 的相同可还原性来证明 2-CNF-SAT 在 NPC 中。我不明白为什么 2-CNF SAT 在 P 中。

Answer 1

为什么 2-CNF SAT 在 P

因为有一个多项式算法来解决它。

证明的粗略草图：

请注意，2-CNF 中的任何子句都采用A => BwhereA和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 OR lit_2 OR ... OR lit_n 这样的子句，并用两个子句 lit_1 OR lit_2 OR ... OR lit_{floor(n/2)} OR 替换它var, lit_{floor(n/2) + 1} OR ... OR lit_n OR NOT var。如果您尝试以这种方式破解具有三个文字的子句，您将得到另一个包含三个文字的子句，因此相同的证明不适用于 2-CNF SAT（并且可能有充分的理由）。