为什么Max-2sat不在P中？

Question

max-2-sat定义如下。给我们一个2-CNF公式和一个绑定的k，并要求找到至少满足该子句k的变量的分配。

我可以理解用于证明2-SAT的技巧是在P中。您使用单位传播使用矛盾。但是，我想知道为什么Max 2-Sat逃脱了。

另外，我发现很难相信这是NP完整的。当然，导致它爆炸的问题是什么。

为什么不像这样的算法。给定2个SAT表达。找到它的长度，我们可以在P中进行。

因此，我们只需检查$ binom nk $ pasibilsions，然后在N 2-SAT表达式的每个子表达式上像喇叭算法一样运行。当然，问题在哪里，因为我们只是运行P算法的多项式时间。

所以我很困惑。我有类似的问题，我有分解，如果是在p或np中。

Answer 1

观察表达式$ {n select k} $可能是$ n $中的指数（例如$ k = n/2 $）。

分解肯定在NP中。我们不知道是否在P中。这是一个主要的公开问题。分解为BQP中的事实证明了它可能不是NP完整的（因为其他NP完全问题在BQP中不知道）