最大2-SAT是多项式时间可将其降低到2-SAT？

Question

我知道在多项式时间中2-sat可解决，2-sat是np-clyp。

我有关于这个陈述的问题： MAX 2-SAT是多项式时间可将其降低到2-SAT。你能向我解释一下如何减少样子？我需要唯一的完整，而不是证据。

Answer 1

我觉得这里有一些混乱。MAX-2-SAT是NP-HARD（其决策版本为NP-COMPERT），而2-SAT在P处于P，因此也在NP中。这意味着2-SAT是MAX-2-SAT的（决定版本）的多项式时间。除非p= np，否则逆转不是真的。

let $ \ phi $ 与 $ m $ 条文有2-sat公式。 如果您真的想减少一个实例 $ \ phi $ 2-sat到（决定版本的）max-2-sat，那么这只是检查是否至少 $ m $ $ \ phi $ 是满意的。