計算複雑性理論
co-NPクラスはNP問題の補問題の集合である(すなわち、「はい」と「いいえ」が逆転している問題)。両者は等しくないと考えられているが証明されていない。2つの複雑性クラスが等しくないことが判明すると、NP完全問題は co-NP には含まれず、co-NP完全問題は NP には含まれないことが明らかになる。