2-CNF可满足性问题属于P类问题，而3-CNF可满足性问题属于NP完全问题。

Question

2-CNF可满足性问题属于P类问题，而3-CNF可满足性问题属于NP完全问题。

6

我非常困惑为什么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。

- Rave

请注意，P是NPC的子集。证明2-CNF SAT属于P同时也证明它属于NPC。 - Antti Huima

既然它在P中，那么它也在NP中，因此我必须证明它是NP难的，才能使其成为NPC问题，这样某些问题就可以同时属于P和NPC了吗？ - Rave

哦，是的，抱歉我回答得太快了，把NP和NPC混淆了:) 抱歉:) 当然不是NPC。你理解上的实际问题在于你无法将SAT简化为2-SAT，简化会失败。 - Antti Huima

请注意，P是NPC的子集。只有当P=NP时才成立。P是NP的子集，我们不知道它是否是NPC的子集。 - Undreren

@Undreren 是的，你说得对。我不知道去年十二月我在想什么。 - Antti Huima

2个回答

3

从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（可能有很好的理由）。

- Per

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jpalecek · Accepted Answer

为什么2-CNF SAT在P类问题中？

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

一个简要证明的草图：

注意，2-CNF中的任何子句都是形如"A => B"的格式，其中A和B都是变量或其否定。因此，我们可以知道这个子句说的是当A为真时，它强制B为真。这也意味着当B为假时，它会强制A为假。我们稍后必须考虑到这一点。

现在，您可以逐个选择一个变量，并搜索是否会转换地强制自己成为其相反的值（A => B => C => … => 非A），反之亦然（非A => ... => A）。如果第一个条件为真，则A必须为假；如果第二个条件为真，则A为真。如果两个条件都满足，则公式是不可满足的。

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

请注意，这个“粗暴”的算法并不是实际使用图的强连通分量的算法，我建议您阅读相关内容。然而，它是多项式的（寻找一个变量的搜索显然是O（N ^ 2），因为您强制考虑每次一个变量，其中包含O（N）子句，而您考虑O（N）变量，这意味着该算法是多项式的）。请注意，子句中最多有两个文字是至关重要的。如果子句是"A => B or C"或其他什么，那么它的效果就不好。