出典: フリー百科事典『ウィキペディア（Wikipedia）』
co-NPとは計算量理論における問題クラスの一つである。
co-NP は次の定義で表される問題のクラスである、﹁ある決定問題Sの補問題 がクラス NPに属する場合、Sはクラス co-NP に属する﹂。ここでいう補問題とは決定問題の yes とnoが逆になった問題である。例えば﹁ある数Nは素数か?﹂という問題の補問題は﹁ある数Nは合成数か?﹂ということになる。P ⊆ NP 同様 P ⊆ co-NP であることがわかっている。
もし P=NP であると仮定した場合は NP=co-NP になる。ここから対偶を取ると NP≠co-NP なら P≠NP になると証明できる。このため NP≠co-NP を証明する事はP≠NP予想に対する有力な解決手段の一つと初期の頃は考えられていた。しかし、この問題は現在も未解決であり、P≠NP を証明することと同様かそれ以上に難しいと推測されている。
関連項目[編集]
|
|---|
| 実用的な時間で解けるクラス |
|
|---|
| 実用的な時間で解けないと疑われているクラス |
|
|---|
| 実用的な時間では解けないクラス |
|
|---|
| クラス階層 |
|
|---|
| クラスの族 |
|
|---|
 一覧・ カテゴリ |
