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 を証明しょうめいすることと同様どうようかそれ以上いじょうに難むずかしいと推測すいそくされている。
