MAX 3 SAT NP-complete或co-NP-complete？

我看到有關此問題的許多衝突信息。有些網站說它是NP完整的，而另一些網站則說它是NP-complete。我能找到的唯一真正一致的信息是絕對是NP難。這是什麼？爲什麼？MAX 3 SAT NP-complete或co-NP-complete？

2014-12-04 STaron1

這個問題似乎是脫離主題，因爲它是關於CS理論。它屬於https://cstheory.stackexchange.com/ – 2014-12-04 21:25:10

@GabeKopley cstheory是研究級CS問題。這可能更適合cs.stackexchange.com。 – templatetypedef 2014-12-04 21:50:02

這個問題似乎是無關緊要的，因爲它涉及複雜性理論，但不是複雜性理論中的研究級問題，因此可能最適合cs.stackexchange.com。 – templatetypedef 2014-12-04 21:50:57

我認爲這取決於你如何定義MAX-3SAT。

如果您將MAX-3SAT定義爲「給定3CNF公式，產生最大化滿足子句數量的變量賦值」的函數問題，那麼它既不是NP完全的也不是共NP完全的。 NP和co-NP是決策問題的類別，因此功能問題不屬於它們。因此，MAX-3SAT不能屬於NP或者NP-NP，所以對任何一個類都不是完全問題。這個功能問題通過減少香草3SAT而成爲NP-hard - 如果你能找到最滿意的任務，你可以通過查看所有的子句是否滿足來檢查原始公式是否可以滿足。

您也可以將MAX-3SAT定義爲決策問題「給定3CNF公式和數字n，確定是否有至少n個子句爲真的公式的變量賦值。」這絕對是在NP中，也是通過從3SAT減少NP-complete。另一方面，如果你將MAX-3SAT定義爲決策問題「給定一個3CNF公式和對該公式的變量賦值，那麼賦值是最大化滿足子句數目的那個賦值嗎？」，那麼它會屬於合作NP（如果答案是否定的，您可以通過展示更好的滿意作業來證實這一點）。不過，我不確定這是否是NP難度，我也不確定是否NP-NP。

希望這會有所幫助！

來源

2014-12-04 21:40:11 templatetypedef

MAX 3 SAT NP-complete或co-NP-complete？

回答

相關問題