我一直在阅读这篇文章，它尝试并解释了 max 2 sat 问题本质上是一个 3-sat 问题并且是 NP-hard 的。
但是，如果您看到这篇文章，我无法理解为什么，在ci满足之后，10 条中有 7 条满足，如果不满足，10 条中有 6 条满足。
有人可以简单地向我解释一下，并揭开这篇文章到底想表达什么的神秘面纱吗？本质上，我已经知道 max-2-sat 问题与 3 sat 问题相同。问题是我无法理解为什么。
更正式地说，我希望解决这个问题：
考虑如下描述的问题 MAX2SAT。
给定一个 2-CNF（连接范式）布尔表达式（有 m 个子句，n 个变量）和一个整数 k，确定是否有一个赋值至少满足总子句中的“k”个？计算 MAX2SAT 的复杂度等级（P 或 NP 或 NP Complete）并说明理由。
好吧，我们应该首先讨论的一个关键误解是，这并没有像您的标题所说的那样将 Max-2-sat 减少到 3-sat。为了证明某事（在本例中为 Max-2-sat）是 np-hard，我们必须相反并将 3-sat（或任何其他已知的 np-hard 问题）归结为它。
如果我们这样做，那么我们表明如果我们减少到 (max-2-sat) 的东西不是 np-hard THEN 3-sat 也不是，因为我们可以做我们的减少并有效地解决 3-sat通过 max-2-sat。我们知道这是不可能的（3-sat 被称为 np-complete，其他人做了艰苦的工作）所以 max-2-sat 不是 np-hard 的想法是矛盾的。
减少到 3-sat 并不能告诉我们太多。在这种情况下，Max-2-sat 仍然很容易。在那种情况下，也许减少到 3-sat 只是一个坏主意，直接解决它更容易。它只是做相反的事情来证明你想要展示的东西