Loading article…
計算複雑性理論では、co-NPは複雑性クラスです。決定問題X が co-NP のメンバーとなるのは、その補問題 X が複雑性クラスNPに属する場合のみです。このクラスは次のように定義できます。決定問題が co-NP に属するのは、すべてのnoインスタンスに対して多項式長の「証明書」があり、証明書とされるものを検証するために使用できる多項式時間アルゴリズムがある場合のみです。
つまり、co-NPとは、多項式 と多項式時間の制限付きチューリングマシン Mが存在し、すべてのインスタンスxに対して、x が非インスタンスであるための必要条件は、長さ で制限された何らかの証明書cに対して、チューリングマシンM がペア( x、c )を受け入れることである。[1]
補完的な問題
NP 問題では、与えられたインスタンスがyesインスタンスであるかどうかを尋ねますが、その補問題は、インスタンスがnoインスタンスであるかどうかを尋ねます。つまり、補問題は co-NP にあるということです。元の NP 問題のyesインスタンスは、その補問題ではnoインスタンスになり、その逆も同様です。
不満足
NP 完全問題の例としては、ブール充足可能性問題があります。ブール式が与えられた場合、それは充足可能でしょうか(式が true を出力する可能性のある入力はあるでしょうか)? 補足問題は、「ブール式が与えられた場合、それは充足不可能でしょうか(式へのすべての可能な入力が false を出力するでしょうか)?」と尋ねます。これは充足可能性問題の補足であるため、 noインスタンスの証明書は、元の NP 問題のyesインスタンスの証明書と同じです。つまり、式を true にするブール変数割り当てのセットです。一方、補足問題 (どのような形式であっても) のyesインスタンスの証明書は、元の NP 充足可能性問題のnoインスタンスの証明書と同じくらい複雑です。
共NP完全性
問題Lがco-NP 完全であるためには、L がco-NP に属し、 co-NP に属する任意の問題に対して、その問題からLへの多項式時間還元が存在する必要があります。
トートロジー削減
命題論理における式がトートロジーであるかどうかを判断することは、共NP完全である。つまり、式がその変数へのあらゆる可能な割り当てにおいて真であると評価されるかどうかである。[1]
他のクラスとの関係
多項式時間で解ける問題のクラスであるPは、NP と co-NP の両方の部分集合である。 P はどちらの場合も厳密な部分集合であると考えられる。 P は相補性の下で閉じており、NP と co-NP は相補的であるため、一方の場合には厳密でありながらもう一方の場合には厳密でないということはあり得ない。つまり、 P が NP に等しい場合、それは co-NP にも等しくなければならず、その逆もまた同様である。[2]
NP と co-NP も不等であると考えられています。[3]そうであれば、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 に属するかどうかも簡単である。すべてn以上のmの素因数をリストアップするだけでよく、検証者は乗算とAKS 素数性テストによってその正当性を確認できる。因数分解の多項式時間アルゴリズムがあるかどうか、つまり整数因数分解が P に属するかどうかは現在分かっていない。そのため、この例は NP と co-NP に属することが分かっているが P に属することは分かっていない最も自然な問題の 1 つとして興味深い。[5]
参考文献
- ^ ab アローラ、サンジーヴ、バラク、ボアズ (2009)。複雑性理論：現代的アプローチ。ケンブリッジ大学出版局。p. 56。ISBN 978-0-521-42426-4。
- ^ マヨルドモ、エルビラ(2004)。 「P対NP」。サラゴサのレアル科学アカデミーのモノグラフ。26：57～68。
- ^ ホップクロフト、ジョン E. (2000)。オートマトン理論、言語、計算入門(第 2 版)。ボストン: アディソンウェスレー。ISBN 0-201-44124-1。第11章。
- ^ Goldreich, Oded (2010). P、NP、NP完全性: 計算複雑性の基礎ケンブリッジ大学出版局p. 155. ISBN 9781139490092。
- ^ アーロンソン、スコット(2016)。「P ≟ NP」(PDF)。ジョン・フォーブス・ジュニア・ナッシュ、マイケル・Th・ラシアス (編)。数学における未解決問題。シュプリンガー・インターナショナル・パブリッシング。pp. 1–122。doi : 10.1007 / 978-3-319-32162-2_1。ISBN 9783319321622。本書のセクション 2.2.4「因数分解とグラフ同型性」の 19 ～ 20 ページ (リンクされたバージョンでは 17 ～ 18 ページ) を参照してください。
外部リンク
- 複雑性動物園:coNP