NP和co-NP有什麼區別

Question

我知道他們完整的對應意味着 NP-完成是NP問題中最難的，並且NP-complete意味着最難在共NP問題，但是最後的區別是二？我的教科書上寫着「是，否則倒過來」，這不會給我留下太多線索。

Answer 1

當您想證明問題的難度時，您必須將其轉化爲稱爲決策問題的東西，這意味着「是/否」答案類型問題。例如，在Set Cover中，我們可能會問「我們能否僅使用X個子集涵蓋所有元素？」其中X是一些任意數字。我們可以證明這個問題存在於NP中，因爲它的解決方案很容易驗證;你提供X子集，然後檢查所有元素是否在多項式時間內被覆蓋。如果我們能夠有效回答「是」決策問題，那麼我們可以最小化X，從而有效解決整個集合覆蓋問題（從而證明P = NP）。

Co- *（Co-NP，Co-NP-complete）側重於回答「否」來補充決策問題。例如，Set Cover的補充決策問題是「對於X個子集的每個組合，是否不可能涵蓋所有元素？」回答「不」這個問題需要你提供一個反例。

總之：NP是關於某個決策問題的「是」的答案。 Co-NP關注的是對於相同但是補充的決策問題的「否」答案。