co-NP
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/11/08 07:44 UTC 版)
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 を証明することと同様かそれ以上に難しいと推測されている。
関連項目
|
||||||||||||
coNP
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/16 08:14 UTC 版)
NP問題の補問題からなるクラスをcoNPという。NP≠coNPならば、P≠NPとなることが示されている。
※この「coNP」の解説は、「P≠NP予想」の解説の一部です。
「coNP」を含む「P≠NP予想」の記事については、「P≠NP予想」の概要を参照ください。
ウィキペディア小見出し辞書の「Co-NP」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- Co-NPのページへのリンク
