反NP
维基百科，自由的百科全书
在計算複雜度理論上, 類反NP是複雜度類的其中一類。一個問題
是反NP的成員，若且唯若，它的補全必定是在複雜類NP；用數學符號來寫，
。簡單來說，類反NP是高效率地以及可核實地證明命題為"錯"的組群，當中的佼佼者是立即找到反例存在。
其中一個NP完全問題的例子是子集總和問題: 被給有限套整數那裡求和到零的一個non-empty 子集? 補全問題是在co NP 和要求: 給有限套整數做每個非空子集有一個非零總和? 給出事例你的證明必須"沒有" 指定求和到零的一個non-empty 子集。這證明然後容易核實。
P, 多項時間可解的問題組, 是一個子集NP 和co NP 。P 認為是一個嚴密的子集在兩個案件(和不能可示範地是嚴密的在一個案件而是不是其他) 。NP 和co NP 並且認為是不公平的。如果那樣, NP 完全問題無法然後是在co NP 並且co NP 完全問題無法是在NP 。 這可能被顯示如下。
假設, 有是在co NP 的一個NP 完全問題。因為所有問題在NP 可能被減少到這個問題它隨後而來那為所有問題在NP 我們能修建決定問題補全在多項時間, 即, NP 是一個子集co NP 的一個非判定性的Turing 機器。從這它隨後而來, 套問題的補全在NP 是套的一個子集問題的補全在co NP, 即, co NP 是一個子集NP 。因為我們已經知道NP 是一個子集co NP 它隨後而來, 他們是相同。證明為事實co NP 完全問題無法是在NP 是對稱的。
如果問題可能被顯示是在NP 和co NP, 那一般被接受作為有力的證據, 問題大概不是NP 完全的(從否則NP = co NP) 。
是問題的例子知道是在NP 和在co NP 是整數工廠化: 被測量的正面整數m 和n 確定如果m 有一個因素比n 和大於一個。一個方向是清楚的; 如果m 有這樣因素長的分裂然後是證明。另一方向是輕微地更加微妙的; 你必須列出m 頭等因素和為每一個提供primality 證明。
整數工廠化與緊密地相關的primality 問題經常被混淆。這並且為人所知是在NP 和co NP, 正工廠化是。但是primality 在在P 。參考: http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf
[编辑] 參考資料
- Complexity Zoo: coNP
| 重要的 複雜度類 (more) |
|---|
| P • NP • 反NP • NP完備 • 反NP完備 • NP-hard • UP • #P • #P-C • L • NL • NC • P完備 • PSPACE • PSPACE完備 • EXPTIME • EXPSPACE • PR • RE • 反RE • RE完備 • 反RE完備 • R • BQP • BPP • RP • ZPP • PCP • IP • PH |
