反np, 在計算複雜度理論上, 類是複雜度類的其中一類, 目录, 定義, 與其他複雜度的關係, 應用, 文內注釋, 參考資料, 外部連結定義, 编辑一個問題x, displaystyle, mathcal, nbsp, 是的成員, 若且唯若, 它的補全x, displaystyle, mathcal, nbsp, 必定是在複雜度np, 用數學符號來寫, displaystyle, mathbf, conp, mathbf, nbsp, 簡單來說, 複雜度, 是高效率而又可核實地證明命題為錯的組群, 當中的佼佼者是立. 在計算複雜度理論上 反NP類是複雜度類的其中一類 目录 1 定義 2 與其他複雜度的關係 3 應用 4 文內注釋 5 參考資料 6 外部連結定義 编辑一個問題X displaystyle mathcal X nbsp 是反NP的成員 若且唯若 它的補全X C displaystyle mathcal X rm C nbsp 必定是在複雜度NP 用數學符號來寫 C o N P L L C N P displaystyle mathbf CoNP L L rm C in mathbf NP nbsp 簡單來說 反NP複雜度 是高效率而又可核實地證明命題為錯的組群 當中的佼佼者是立即找到反例存在 其中一個NP完全問題的例子是子集合加總問題 給一個整數集合 問是否存在某個非空子集中的數字和為0 例 給定集合 7 3 2 5 8 答案是是 因為子集合 3 2 5 的數字和是0 補全問題在反NP中就會要求 給有限的整數集 是否每個非空子集之總和皆不為0 你的證明只要必須給出事例 敘述 沒有 指定求和到零的一個非空子集 而這證明必須可以在合理時間內驗證 與其他複雜度的關係 编辑複雜度P 是多項式時間可解的問題集合 是一個NP和反NP的子集 P通常認定是一個在此兩類別下的嚴格子集 但無法驗證是落在兩個集合的哪一邊 NP和反NP通常認為是不相等的 如果那樣 NP完全問題將不會落在反NP問題中 且反NP完全問題將不會落在NP中 本問題可由下述步驟粗略證明 假設有個NP完全問題X displaystyle mathcal X nbsp 處於反NP問題的集合中 由於所有NP問題可被變換成X displaystyle mathcal X nbsp 問題 因此我們可以為所有NP問題建造一個可在多項式時間判定其補性質的非確定型圖靈機 意即NP是反NP的子集 因此NP問題的補集合是一個反NP問題的補集合的子集 意即反NP是NP的子集 由於我們已知NP是反NP的子集 因此表示這兩個集合是一樣的 這證明了沒有反NP完全問題可在NP類之中的性質是對稱的 Symmetrical 用數學符號嚴格證明 假設一個問題X displaystyle mathcal X nbsp 是NP完全 N P C o N P displaystyle mathbf NP mathbf CoNP nbsp 若且唯若X C o N P displaystyle mathcal X in mathbf CoNP nbsp 以下的證明是不能從以上文字直接看得出 displaystyle Rightarrow nbsp 若N P C o N P displaystyle mathbf NP mathbf CoNP nbsp X N P X C o N P displaystyle mathcal X in mathbf NP Rightarrow mathcal X in mathbf CoNP nbsp dd dd displaystyle Leftarrow nbsp N P C o N P displaystyle mathbf NP subseteq mathbf CoNP nbsp 如果L N P displaystyle mathcal L in mathbf NP nbsp 很明顯地 若X displaystyle mathcal X nbsp 是NP完全 自然X displaystyle mathcal X nbsp 是NP難 L p X displaystyle mathcal L leq p mathcal X nbsp 所以L C p X C displaystyle mathcal L mathrm C leq p mathcal X mathrm C nbsp 但X C o N P displaystyle mathcal X in mathbf CoNP nbsp 亦即代表X C N P displaystyle mathcal X mathrm C in mathbf NP nbsp 所以L C N P displaystyle mathcal L mathrm C in mathbf NP nbsp 最終 L C o N P displaystyle mathcal L in mathbf CoNP nbsp N P C o N P displaystyle mathbf NP supseteq mathbf CoNP nbsp X C o N P X C N P X C C o N P X C C X N P displaystyle mathcal X in mathbf CoNP Rightarrow mathcal X mathrm C in mathbf NP Rightarrow mathcal X mathrm C in mathbf CoNP Rightarrow mathcal X mathrm C mathrm C mathcal X in mathbf NP nbsp dd dd 如果一個問題可被證同時為NP與反NP 則通常我們將會視作本問題不是NP完全命題的強力假設 若非如此 則NP相等於反NP 應用 编辑一個同時在NP與反NP集合的有名問題是整數分解 給兩個正整數m與n 決定m是否有小於n且大於1的因數 第一個问题的方法很清晰 如果m的確存在一個滿足條件的因子 則長除法即可驗證 另一個问题的方法就困難且精妙多了 你必須將m的所有質數因子列出 並為每個因子提供質數性質的證明 整數因子分解常與質數性質問題混淆在一起 整數因子化據信是NP或反NP 而質數問題落在類別P 1 文內注釋 编辑 參考 http www math princeton edu annals issues 2004 Sept2004 Agrawal pdf 页面存档备份 存于互联网档案馆 參考資料 编辑 英文 複雜度類動物園 反NP外部連結 编辑Complexity Zoo coNP 取自 https zh wikipedia org w index php title 反NP amp oldid 71207926, 维基百科,wiki,书籍,书籍,图书馆,