Co-NP

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 を証明することと同様かそれ以上に難しいと推測されている。

関連項目

• 計算量理論
• NP
• P (計算量理論)

表 話 編 歴 主な複雑性クラス
実用的な時間で解けるクラス	DLOGTIME AC0 ACC0 TC0 L SL RL NL NC SC CC P P完全 ZPP RP BPP BQP APX
実用的な時間で解けないと疑われているクラス	UP NP NP完全 NP困難 co-NP co-NP完全 AM QMA PH ⊕P PP #P #P完全 IP PSPACE
実用的な時間では解けないクラス	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL
クラス階層	多項式階層 指数階層 グジェゴルチク階層 算術的階層 ブーリアン階層
クラスの族	DTIME NTIME DSPACE NSPACE PCP 対話型証明系
一覧・ カテゴリ