怎么2-CNF SAT在P，而3-CNF SAT在NPC？
我真的很困惑为什么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中。
I am really confused why 2-CNF SAT is in P, while 3-CNF SAT is in NPC. I Read CLRS, and I understand how they prove 3-CNF SAT is in NPC. Can't I use the same reducibility from SAT to 2-CNF-SAT to prove 2-CNF-SAT is in NPC. I don't understand why 2-CNF SAT is in P.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
因为有多项式算法可以解决。
证明的粗略草图：
请注意，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 或 C或其他东西，它不会工作得那么好。Because there is a polynomial algorithm to solve it.
A rough sketch of a proof:
Note that any clause in 2-CNF is in the form
A => BwhereAandBare either variables or their negation. Therefore, we can tell that this clause says when A is true, it forces B to be true. It also means that B is false forces A to be false. We have to consider that later.Now, you can take a variable, one by one, and search if it transitively forces itself to be its negative (A => B => C => ... => non A) and vice versa (non A => ... => A). If the first is true, A has to be false; if the second, A is true. If both, the formula is unsatisfiable.
If you don't find any variable that makes the formula unsatisfiable, it is satisfiable.
Note that this "brutal" algorithm is not the actual one using strongly connected components of a graph, which I recommend you to read on. Yet, it is polynomial (the search for one variable is clearly O(N^2), since you force one variable at a time considering O(N) clauses and you consider O(N) variables, which means the algorithm is polynomial). Note that the fact that we have at most two literals in a clause is crucial. If the clauses were
A => B or Cor something, it wouldn't work as good.从 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} 或 ... 或 lit_n 或非 var。如果您尝试以这种方式破解具有三个文字的子句，您将得到另一个具有三个文字的子句，因此相同的证明不适用于 2-CNF SAT（可能有充分的理由）。
The canonical reduction from CNF SAT to 3-CNF SAT is to take a clause like lit_1 OR lit_2 OR ... OR lit_n and replace it with two clauses 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. If you try to crack a clause with three literals this way, you'll get another clause with three literals, so the same proof won't work for 2-CNF SAT (and probably for good reason).