我一直在阅读这篇文章，它试图解释为什么最大 2 sat 问题本质上是一个 3 sat 问题并且是 NP 困难的。
但是，如果你看到这篇文章，我无法理解为什么在ci满意之后，10个条款中有7个是满意的，如果不满意，10个条款中有6个是满足的。
有人可以用简单的术语向我解释，并揭开文章到底想传达什么吗？从本质上讲，我已经知道最大 2 个卫星问题与 3 个卫星问题相同。问题是我无法理解为什么。
更正式地说，我希望解决这个问题：
请考虑MAX2SAT描述的问题，如下所示。
给定一个 2-CNF(合取范式(布尔表达式(带有 m 子句，n 个变量(和一个整数 k，确定是否存在 转让至少满足总条款的"k"？计算 复杂度类(P 或 NP 或 NP 完成(的MAX2SAT 理由。
好吧，我们应该首先讨论的一个关键误解是，这并不是像您的标题所说的那样将 Max-2-sat 减少到 3-sat。为了证明某物(在本例中为 Max-2-sat(是 np-hard，我们必须反其道而行之，将 3-sat(或任何其他已知的 np-hard 问题(简化为它。
如果我们这样做，那么我们就会证明，如果我们简化为(max-2-sat(的东西不是np-hard THEN 3-sat，因为我们可以通过max-2-sat有效地进行归约并解决3-sat。我们知道这是不可能的(3-sat 是已知的 np-complete，其他人做了艰苦的工作(，所以 max-2-sat 不是 np-hard 的想法是一个矛盾。
减少到 3 周六并不能告诉我们太多。在这种情况下，Max-2-sat仍然很容易。在这种情况下，也许减少到 3 周六只是一个坏主意，直接解决它更容易。只有做相反的事情才能证明你想要展示什么