Loading article…
計算複雑性理論において、co-NPは複雑性クラスです。決定問題X が co-NP に属するのは、その補集合X が複雑性クラスNPに属する場合に限ります。このクラスは次のように定義できます。決定問題が co-NP に属するのは、任意のnインスタンスに対して多項式長の「証明書」が存在し、かつ、その証明書を検証するために使用できる多項式時間アルゴリズムが存在する場合に限ります。
つまり、co-NPは多項式が存在する決定問題の集合である。また、多項式時間で制限されたチューリングマシンMが存在し、すべてのインスタンスxに対して、 xがインスタンスでないのは、次の場合に限る：長さが制限されたある可能な証明書cに対して、 、チューリングマシンMはペア( x , c )を受理する。 [ 1 ]
NP問題は、与えられたインスタンスが「はい」インスタンスであるかどうかを問う問題であるのに対し、その補集合は、インスタンスが「いいえ」インスタンスであるかどうかを問う問題であり、つまり補集合はco-NPに属する。元のNP問題における「はい」インスタンスは、その補集合における「いいえ」インスタンスとなり、その逆もまた同様である。
NP完全問題の一例として、ブール充足可能性問題があります。これは、ブール式が与えられたとき、それが充足可能かどうか（式が真を出力するような入力が存在するかどうか）を問う問題です。補完的な問題は、「ブール式が与えられたとき、それが充足不可能かどうか（式へのすべての可能な入力が偽を出力するかどうか）？」と問うものです。これは充足可能性問題の補完問題であるため、 no -instanceの証明書は、元のNP問題のyes -instanceの証明書と同じです。つまり、式を真にするブール変数の割り当ての集合です。一方、補完的な問題のyes -instanceの証明書（どのような形式であっても）は、元のNP充足可能性問題のno -instanceの証明書と同じくらい複雑になります。
問題Lがco-NP 完全であるのは、Lが co-NP に属し、かつ co-NP に属する任意の問題に対して、その問題からLへの多項式時間還元が存在する場合に限る。
命題論理における式がトートロジーであるかどうかを判定することはco-NP完全である。つまり、その式が変数へのあらゆる可能な割り当ての下で真と評価される場合である。[ 1 ]
多項式時間で解ける問題のクラスであるP は、NP と co-NP の両方の部分集合です。P はどちらの場合も厳密な部分集合であると考えられています。P は補集合に関して閉じており、NP と co-NP は補集合であるため、一方の場合に厳密で他方の場合に厳密でないということはあり得ません。P が NP と等しい場合、P は co-NP とも等しくなければならず、その逆もまた然りです。 [ 2 ]
NPとco-NPは等しくないと考えられており[ 3 ]、両者が等しいとすれば、多項式階層PHがNPに崩壊することになる。両者が等しくない場合、NP完全問題はco-NPに存在できず、co-NP完全問題もNPには存在できない[ 4 ] 。これは次のように示すことができる。矛盾を生じさせるために、co-NPに属するNP完全問題Xが存在すると仮定する。NPに属するすべての問題はX に還元できるため、NPに属するすべての問題について、その補集合を多項式時間で決定する非決定性チューリングマシンを構築できる。すなわち、。このことから、NP の問題の補集合は co-NP の問題の補集合の部分集合であることがわかります。つまり、したがって . co-NP完全問題がNPに属することはないという証明は、 は左右対称です。
co-NPはPHのサブセットであり、PH自体はPSPACEのサブセットである。
NPとco-NPの両方に属することが知られているが、Pに属することは知られていない問題の例として、整数因数分解があります。正の整数mとnが与えられたとき、 mがnより小さく1より大きい因数を持つかどうかを判定します。NPに属することは明らかです。mがそのような因数を持つ場合、因数自体が証明書になります。co-NPに属することも簡単です。mの素因数をすべてn以上として列挙するだけでよく、検証者は乗算とAKS素数判定によってその妥当性を確認できます。因数分解の多項式時間アルゴリズムが存在するかどうか、つまり整数因数分解がPに属するかどうかは現在知られていないため、この例はNPとco-NPに属することが知られているがPに属することは知られていない最も自然な問題の1つとして興味深いものです。[ 5 ]
