co-NPとは何？ わかりやすく解説 Weblio辞書 (original) (raw)
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 を証明することと同様かそれ以上に難しいと推測されている。
関連項目
| 表 話 編 歴 主な複雑性クラス(一覧) | |
|---|---|
| Considered feasible | DLOGTIME AC0 ACC0 TC0 L SL RL NL NC SC CC P P完全 ZPP RP BPP BQP APX |
| Suspected infeasible | UP NP NP完全 NP困難 co-NP co-NP完全 AM QMA PH ⊕P PP #P #P完全 IP PSPACE |
| Considered infeasible | EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL |
| クラス階層 | 多項式階層 指数階層 グジェゴルチク階層 算術的階層 ブーリアン階層 |
| クラスの族 | DTIME NTIME DSPACE NSPACE PCP 対話型証明系 |
coNP
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/16 08:14 UTC 版)
NP問題の補問題からなるクラスをcoNPという。NP≠coNPならば、P≠NPとなることが示されている。
※この「coNP」の解説は、「P≠NP予想」の解説の一部です。
「coNP」を含む「P≠NP予想」の記事については、「P≠NP予想」の概要を参照ください。
ウィキペディア小見出し辞書の「co-NP」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。お問い合わせ。
| 英和和英テキスト翻訳 | >> Weblio翻訳 |
|---|
| 英語⇒日本語日本語⇒英語 | | | ------------ | |
- >> 「co-NP」を含む用語の索引
- co-NPのページへのリンク