algorithm - Max 2 Sat 究竟如何减少到 3 Sat？

Question

我一直在阅读 this文章尝试并解释了 max 2 sat 问题本质上是一个 3-sat 问题并且是 NP-hard。

然而，如果你看到这篇文章，我无法理解为什么，满足ci后，10个子句中有7个是满意，如果不满意，则满足 10 个条款中的 6 个。

有人可以简单地向我解释一下，并揭开这篇文章到底想表达什么吗？本质上，我已经知道 max-2-sat 问题与 3 sat 问题相同。问题是我不明白为什么。

更正式地说，我希望解决这个问题:

Consider the problem MAX2SAT described as follows.

Given a 2-CNF (Conjunctive Normal Form) Boolean expression (with m clauses, n variables) and an integer k, Decide if there is an assignment satisfying at least ‘k’ of the total clauses? Compute the complexity class (P or NP or NP Complete) of the MAX2SAT with justification.

Answer 1

嗯，我们应该首先讨论的一个关键误解是，这并没有像您的标题所说的那样将 Max-2-sat 减少到 3-sat。为了证明某些东西(在本例中为 Max-2-sat)是 np-hard，我们必须相反并将 3-sat(或任何其他已知的 np-hard 问题)化简为它。

如果我们这样做，那么我们证明如果我们减少到 (max-2-sat) 的东西不是 np-hard THEN 3-sat 也不是因为我们可以减少并解决 3 - 通过 max-2-sat 有效地坐着。我们知道这是不可能的(3-sat 是已知的 np-complete，其他人做了艰苦的工作)所以 max-2-sat 不是 np-hard 的想法是矛盾的。

减少到 3-sat 并不能告诉我们太多。在那种情况下，Max-2-sat 仍然很容易。在那种情况下，也许减少到 3-sat 只是一个坏主意，直接解决它更容易。只有做相反的事情才能证明你想要展示的东西