共NP完全

計算量理論では、 co-NP 完全な計算問題は、 co-NPにおける最も難しい問題であり、co-NP のあらゆる問題は、多項式のオーバーヘッドのみを伴う co-NP 完全問題の特殊なケースとして再定式化できるという意味です。P が co - NP と異なる場合、すべての co-NP 完全問題は多項式時間で解くことはできません。co-NP 完全問題を迅速に解く方法が存在する場合、そのアルゴリズムを使用してすべての co-NP 問題を迅速に解くことができます。

それぞれの co-NP 完全問題は、NP 完全問題の補問題です。NPとco - NPの両方にいくつかの問題があります。たとえば、Pのすべての問題や整数因数分解などです。ただし、セットが等しいかどうかは不明ですが、不等である可能性が高いと考えられます。詳細については、 co-NPとNP 完全を参照してください。

1979年にフォーチュンは、任意のスパース言語が共NP完全（または共NP困難）である場合、P = NP^{であることを示しました[1] 。これは}マハニーの定理の重要な基礎です。

決定問題 Cは、それがco-NPに属し、かつ co-NP のすべての問題が多項式時間でそれに多対一還元可能である場合、 co-NP 完全である。^[2]これは、すべての co-NP 問題Lに対して、 Lの任意のインスタンスを同じ真理値を持つCのインスタンスに変換できる多項式時間アルゴリズムが存在することを意味します。結果として、Cに対して多項式時間アルゴリズムがあれば、すべての co-NP 問題を多項式時間で解決できます。

共NP完全問題の一例はトートロジーである。これは与えられたブール式がトートロジーであるかどうかを判断する問題である。つまり、変数に真偽値を割り当てるすべての可能な方法が真のステートメントを生成するかどうかである。これは、そのような割り当てが少なくとも1つ存在するかどうかを問うブール充足可能性問題と密接に関連しており、NP完全である。^[2]

• 複雑性動物園：coNPC