NP完全性

計算複雑性理論では、問題がNP 完全であるとは、次の場合を指します。

これは決定問題であり、問題への入力に対して、出力は「はい」または「いいえ」のいずれかになります。
答えが「はい」の場合、これは短い（多項式の長さの）解の存在を通じて実証できます。
各ソリューションの正しさは迅速に（つまり、多項式時間で）検証でき、ブルートフォース検索アルゴリズムはすべての可能なソリューションを試すことでソリューションを見つけることができます。
この問題は、解決策が正しいことをすぐに検証できる他のすべての問題をシミュレートするために使用できます。この意味で、NP 完全問題は、解決策がすぐに検証できる問題の中で最も難しい問題です。NP 完全問題の解決策をすぐに見つけることができれば、特定の解決策を簡単に検証できる他のすべての問題の解決策もすぐに見つけることができます。

「NP 完全」という名前は、「非決定性多項式時間完全」の略です。この名前の「非決定性」は、非決定性チューリングマシンを指し、総当たり検索アルゴリズムの考え方を数学的に形式化する方法です。多項式時間とは、決定性アルゴリズムが単一のソリューションをチェックする場合、または非決定性チューリングマシンが検索全体を実行する場合に「速い」と見なされる時間の量を指します。「完全」とは、同じ複雑さのクラスですべてをシミュレートできる特性を指します。

より正確には、問題への各入力は、多項式長の解の集合に関連付けられ、それぞれの妥当性は迅速に（多項式時間で）テストできる必要があります^[2]。つまり、どの入力に対しても、解の集合が空でない場合は出力が「はい」、空の場合は「いいえ」となります。この形式の問題の複雑性クラスは、NPと呼ばれ、「非決定性多項式時間」の略語です。NP 内のすべてが多項式時間でその問題に変換できる場合、その問題はNP 困難であると言われます（NP に含まれていなくても）。問題が NP 完全であるのは、NP に含まれ、かつ NP 困難である場合です。NP 完全問題は、NP で最も難しい問題を表します。NP 完全問題に多項式時間アルゴリズムがある場合、NP 内のすべての問題に多項式時間アルゴリズムがあります。NP 完全問題の集合は、NP-CまたはNPCと表記されることが多いです。

NP 完全問題の解決は「迅速に」検証できますが、迅速に解決する方法は知られていません。つまり、現在知られているアルゴリズムを使用して問題を解決するのに必要な時間は、問題のサイズが大きくなるにつれて急速に増加します。その結果、これらの問題を迅速に解決できるかどうかを判断することは、P 対 NP 問題と呼ばれ、今日のコンピューターサイエンスにおける基本的な未解決問題の 1 つです。

NP 完全問題の解を迅速に計算する方法はまだ発見されていないものの、コンピュータ科学者やプログラマーは依然として NP 完全問題に頻繁に遭遇しています。NP 完全問題は、多くの場合、ヒューリスティックな方法と近似アルゴリズムを使用して解決されます。

概要

NP 完全問題は、多項式時間で解決が検証できるすべての決定問題の集合NPに含まれます。NPは、非決定性チューリングマシンで多項式時間で解決できる決定問題の集合として同等に定義できます。NP 内の問題pは、NP 内の他のすべての問題が多項式時間でpに変換 (または簡約) できる場合、NP 完全です。^[^{引用が必要}^]

NP のすべての問題がすぐに解決できるかどうかはわかっていません。これは P 対 NP 問題と呼ばれます。しかし、NP 完全問題がすぐに解決できるのであれば、NPのすべての問題もすぐに解決できます。NP 完全問題の定義では、NP のすべての問題はすべての NP 完全問題にすぐに還元できる (つまり、多項式時間で還元できる) とされているからです。このため、NP 完全問題は一般に NP 問題よりも難しい、または困難であると言われることがよくあります。^[要出典]

正式な定義

決定問題が NP 完全であるとは、次の場合である: ^[^{引用が必要}^] $\scriptstyle C$

$\scriptstyle C$ NPであり、
NPにおけるあらゆる問題は多項式時間で帰着可能である。 ^[3] $\scriptstyle C$

$\scriptstyle C$ の候補解が多項式時間で検証できることを示すことによって、NP に属することが示されます。 $\scriptstyle C$

条件2を満たす問題は、条件1を満たすかどうかに関わらずNP困難であると言われることに注意されたい。 ^[4]

この定義の結果として、に対する多項式時間アルゴリズム（UTM上、または他のチューリングと同等の抽象マシン上）があれば、 NP のすべての問題を多項式時間で解決できることになります。 $\scriptstyle C$

背景

NP完全性の概念は1971年に導入された（クック・レビンの定理を参照）が、NP完全という用語は後になって導入された。1971年のSTOC会議では、NP完全問題が決定論的チューリングマシンで多項式時間で解けるかどうかについて、コンピュータ科学者の間で激しい議論があった。ジョン・ホップクロフトは、NP完全問題が多項式時間で解けるかどうかという問題は、どちらの主張にも正式な証明がないため、後日解決するよう延期すべきであるという点で会議の全員の合意に達した。^[要出典] これは「P=NPかどうかの問題」として知られている。

NP完全問題が実際に多項式時間で解けるかどうかはまだ誰も決定的に判断できていないため、これは数学の未解決の大きな問題の一つとなっている。クレイ数学研究所は、 P=NPまたはP≠NPの正式な証明をした人に100万ドルの賞金（ミレニアム賞）を提供する予定である。^[5]

NP 完全問題の存在は明らかではありません。Cook -Levin 定理は、ブール充足可能性問題はNP 完全であると述べており、したがってそのような問題が存在することを確立しています。1972 年に、Richard Karp は、他のいくつかの問題も NP 完全であることを証明しました ( Karp の 21 NP 完全問題を参照)。したがって、NP 完全問題のクラス (ブール充足可能性問題以外) が存在します。最初の結果以来、以前に NP 完全であることが示された他の問題からの還元によって、他の何千もの問題が NP 完全であることが示されました。これらの問題の多くは、Garey と Johnson (1979) にまとめられています。

NP完全問題

新しい問題が NP 完全であることを証明する最も簡単な方法は、まずそれが NP であることを証明し、次に既知の NP 完全問題をそれに還元することです。したがって、さまざまな NP 完全問題を知っておくと便利です。以下のリストには、決定問題として表現すると NP 完全となる、よく知られている問題がいくつか含まれています。

右側は、いくつかの問題と、それらの NP 完全性を証明するために通常使用される縮約の図です。この図では、問題は下から上に縮約されています。この図は、これらの問題間の数学的関係の説明としては誤解を招く可能性があることに注意してください。任意の 2 つの NP 完全問題間には多項式時間の縮約が存在するためです。ただし、この多項式時間の縮約を実証するのが最も簡単だった場所を示しています。

P の問題と NP 完全問題の間には、わずかな違いしかないことがよくあります。たとえば、ブール充足可能性問題の制限である3 充足可能性問題は NP 完全のままですが、わずかに制限された2 充足可能性問題は P に含まれます (具体的には、NL 完全)。ただし、わずかに一般的な最大 2 充足問題は、やはり NP 完全です。グラフを 2 色で着色できるかどうかを判断することは P に含まれますが、3 色で着色できるかどうかは、平面グラフに制限されている場合でも NP 完全です。グラフがサイクルであるか2部グラフであるかを判断することは非常に簡単です ( L内) が、最大 2 部グラフまたは最大サイクルサブグラフを見つけることは NP 完全です。ナップサック問題の解は、最適解の任意の固定パーセンテージ内で多項式時間で計算できますが、最適解を見つけることは NP 完全です。

中級問題

興味深い例として、グラフ同型性問題があります。これは、2 つのグラフ間にグラフ同型性が存在するかどうかを判断するグラフ理論の問題です。2 つのグラフは、頂点の名前を変更するだけで一方のグラフを他方のグラフに変換できる場合、同型です。次の 2 つの問題を考えてみましょう。

グラフ同型性: グラフ G ₁はグラフ G ₂と同型ですか?
サブグラフ同型性: グラフ G _{1はグラフ G}₂のサブグラフと同型ですか?

部分グラフ同型性問題は NP 完全です。グラフ同型性問題は NP に含まれますが、P でも NP 完全でもないと疑われています。これは、難しいと考えられているが NP 完全ではないと考えられている問題の例です。このクラスはNP 中間問題と呼ばれ、P≠NP の場合にのみ存在します。

NP完全問題を解く

現在、NP完全問題に対する既知のアルゴリズムはすべて、入力サイズの超多項式の時間を必要とします。頂点カバー問題には^[6]があり、より高速なアルゴリズムがあるかどうかは不明です。 $O(1.2738^{k}+nk)$ $k>0$

一般的に、以下の手法は計算問題を解決するために適用でき、多くの場合、大幅に高速なアルゴリズムを生み出します。

近似: 最適なソリューションを探す代わりに、最適なソリューションから最大で 1 倍のソリューションを探します。
ランダム化: ランダム性を利用して平均実行時間を短縮し、アルゴリズムが小さな確率で失敗することを許可します。注:モンテカルロ法は、この特定の意味では効率的なアルゴリズムの例ではありませんが、遺伝的アルゴリズムなどの進化的アプローチはそうである可能性があります。
制限: 入力の構造を制限することにより (たとえば、平面グラフに)、通常はより高速なアルゴリズムが可能になります。
パラメータ化: 入力の特定のパラメータが固定されている場合、高速なアルゴリズムが存在することがよくあります。
ヒューリスティック: 多くの場合「かなりうまく」機能するが、常に高速で常に良い結果を生み出すという証明がないアルゴリズム。メタヒューリスティックなアプローチがよく使用されます。

ヒューリスティックアルゴリズムの一例として、一部のコンパイラのレジスタ割り当てフェーズでグラフの色付けに使用される、最適ではない貪欲な色付けアルゴリズムが挙げられます。この手法は、グラフ色付けグローバルレジスタ割り当てと呼ばれます。各頂点は変数であり、同時に使用されている変数間にはエッジが描画され、色は各変数に割り当てられたレジスタを示します。ほとんどのRISCマシンにはかなり多数の汎用レジスタがあるため、このアプリケーションではヒューリスティックなアプローチでも効果的です。 $O(n\log n)$

異なる種類の還元における完全性

上記の NP 完全の定義では、用語「削減」は、多項式時間の多対一削減という技術的な意味で使用されていました。

もう 1 つのタイプの縮約は、多項式時間チューリング縮約です。多項式時間で解決するサブルーチンが与えられ、このサブルーチンを呼び出して多項式時間で解決するプログラムを作成できる場合、問題は多項式時間チューリング縮約可能です。これは、プログラムがサブルーチンを 1 回しか呼び出せないという制限があり、サブルーチンの戻り値はプログラムの戻り値でなければならないという制限がある多対一縮約とは対照的です。 $\scriptstyle X$ $\scriptstyle Y$ $\scriptstyle Y$ $\scriptstyle X$

NP 完全の類似物を、多対一縮約ではなくチューリング縮約で定義した場合、結果として生じる問題セットは NP 完全よりも小さくなりません。それがより大きくなるかどうかは未解決の問題です。

NP 完全性を定義するためによく使用される別の種類の縮約は、対数空間の多対一縮約です。これは、対数量の空間のみで計算できる多対一縮約です。対数空間で実行できるすべての計算は多項式時間でも実行できるため、対数空間の多対一縮約がある場合は、多項式時間の多対一縮約も存在することになります。この種類の縮約は、より一般的な多項式時間の多対一縮約よりも洗練されており、P 完全などのより多くのクラスを区別できます。これらの種類の縮約で NP 完全の定義が変わるかどうかは、まだ未解決の問題です。現在知られているすべての NP 完全問題は、対数空間縮約で NP 完全です。現在知られているすべての NP 完全問題は、縮約や縮約などのはるかに弱い縮約でも NP 完全のままです。SAT などの一部の NP 完全問題は、多対数時間射影でも完全であることが知られています。^{[7]しかし、}AC ⁰リダクションは多項式時間リダクションよりも厳密に小さいクラスを定義することが知られています。 ^[8] $AC_{0}$ $NC_{0}$

ネーミング

ドナルド・クヌースによると、「NP完全」という名前は、アルフレッド・エイホ、ジョン・ホップクロフト、ジェフリー・ウルマンが彼らの有名な教科書「コンピュータアルゴリズムの設計と分析」で広めた。彼は、理論計算機科学コミュニティで行った投票の結果に従って、本のゲラ刷りで（「多項式完全」から）変更を導入したと報告している。^[9]投票で出された他の提案^[10]には、「ヘラクレス」、「手ごわい」、クックに敬意を表したシュタイグリッツの「ハードボイルド」、シェン・リンの頭字語「PET」などがあった。「PET」は「おそらく指数時間」の略だが、 P対NP問題がどちらの方向に進むかによって、「証明可能な指数時間」または「以前の指数時間」を表す可能性がある。^[11]

よくある誤解

次のような誤解がよくあります。^[12]

「NP 完全問題は、最も難しい既知の問題です。」 NP 完全問題は NP に属するため、実行時間はせいぜい指数関数的です。ただし、プレスブルガー算術など、一部の問題はより多くの時間が必要であることが証明されています。一部の問題では、停止問題など、まったく解決できないことが証明されています。
「NP 完全問題は、非常に多くの異なる解が存在するため困難です。」一方では、解空間が同じくらい大きいが、多項式時間で解決できる問題が多数あります (たとえば、最小全域木)。他方では、ランダム化された多項式時間削減の下で NP 困難である、最大で 1 つの解を持つ NP 問題があります ( Valiant–Vazirani の定理を参照)。
「NP完全問題を解くには指数時間が必要である。」まず、これはP ≠ NPを意味し、これはまだ未解決の問題です。さらに、NP完全問題の中には、O(2 ^{√ n} n )などの超多項式だが指数以下の時間で実行されるアルゴリズムがあるものもあります。たとえば、平面グラフの独立集合問題と支配集合問題はNP完全ですが、平面分離定理を使用して指数以下の時間で解くことができます。^[13]
「NP完全問題の各インスタンスは困難である。」多くの場合、いくつかのインスタンス、またはほとんどのインスタンスは、多項式時間内で簡単に解決できる場合があります。ただし、P = NPでない限り、多項式時間アルゴリズムは、特定のサイズの指数的に多数の入力のうち、多項式を超える数に対して漸近的に間違っている必要があります。^[14]
「P=NP の場合、すべての暗号は解読可能です。」多項式の次数または定数が十分に大きい場合、多項式時間の問題は実際には解くのが非常に困難になる可能性があります。さらに、情報理論的セキュリティは、無制限の計算能力でも解読できない暗号化方法を提供します。
「大規模な量子コンピュータは、NP完全問題を効率的に解くことができるだろう。」フォールトトレラントな量子コンピュータによって（原理的には）効率的に解くことができる決定問題のクラスは、BQPとして知られています。しかし、BQPはNPのすべてを含むとは考えられておらず、そうでない場合は、NP完全問題を一切含むことができません。^[15]

プロパティ

決定問題を何らかの固定されたエンコーディングの形式言語として見ると、すべての NP 完全問題の集合 NPC は次の条件で閉じられません。

NPCが相補性の下で閉じているかどうかは分かっていない。なぜなら、NPC= co-NPCであるためにはNP= co-NPである必要があり、NP=co-NPは未解決の問題だからである。^[16]

参照

参考文献

引用

^ たとえば、各変数にtrue を単純に代入すると、18 番目の結合(したがって完全な式)はfalse になります。 ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$
^ Cobham, Alan (1965). 「関数の本質的な計算難度」Proc. Logic, Methodology, and Philosophy of Science II . ノースホランド。
^ J. van Leeuwen (1998).理論計算機科学ハンドブック. Elsevier. p. 84. ISBN 978-0-262-72014-4。
^ J. van Leeuwen (1998).理論計算機科学ハンドブック. Elsevier. p. 80. ISBN 978-0-262-72014-4。
^ Kiersz, Andy. 「著名な数学者が数学最大の謎の一つを解いたと主張している — それは賞金100万ドルの6つの問題のうちの1つだ」。Business Insider 。 2023年4月24日閲覧。
^ Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2010-09-06). 「頂点カバーの上限の改善」.理論計算機科学. 411 (40): 3736–3756. doi : 10.1016/j.tcs.2010.06.026 . ISSN 0304-3975.
^ Agrawal, M. ; Allender, E.; Rudich, Steven (1998). 「回路の複雑さの削減: 同型定理とギャップ定理」. Journal of Computer and System Sciences . 57 (2): 127–143. doi : 10.1006/jcss.1998.1583 . ISSN 1090-2724.
^ Agrawal, M. ; Allender, E.; Impagliazzo, R.; Pitassi, T. ; Rudich, Steven (2001). 「リダクションの複雑さの軽減」.計算複雑性. 10 (2): 117–138. doi :10.1007/s00037-001-8191-1. ISSN 1016-3328. S2CID 29017219.
^ Don Knuth、Tracy Larrabee、Paul M. Roberts、「Mathematical Writing」、 Wayback Machineに 2010 年 8 月 27 日にアーカイブ§ 25、MAA Notes No. 14 、MAA、1989 ( Stanford Technical Report、1987とも)。
^ Knuth, DF (1974). 「用語提案」SIGACT News 6 ( 1): 12–18. doi :10.1145/1811129.1811130. S2CID 45313676.
^ 世論調査を参照、または[1] Archived 2011-06-07 at the Wayback Machine。
^ ボール、フィリップ（2000）。「DNAコンピューターが巡回セールスマンを支援」ネイチャー。doi：10.1038/news000113-10。
^ ベルン (1990); Deĭneko、Klinz、Woeginger (2006);ドーンら。 (2005);リプトンとタージャン (1980)。
^ Hemaspaandra, LA; Williams, R. (2012). 「SIGACT News 複雑性理論コラム 76」. ACM SIGACT News . 43 (4): 70. doi :10.1145/2421119.2421135. S2CID 13367514.
^ Aaronson, Scott (2010). 「BQP と多項式階層」。Schulman, Leonard J. (編)。Proceedings of the 42nd ACM Symposium on Theory of Computing、STOC 2010、ケンブリッジ、マサチューセッツ州、米国、2010 年 6 月 5 ～ 8 日。Association for Computing Machinery。pp. 141 ～ 150。arXiv : 0910.4698。doi : 10.1145 / 1806689.1806711。ISBN 978-1-4503-0050-6。
^ タルボット、ジョン、ウェルシュ、DJA（2006）、複雑性と暗号化：入門、ケンブリッジ大学出版局、p.57、ISBN 9780521617710NP と co-NP が等しいかどうかという問題は、おそらく P 対 NP の問題に次いで、複雑性理論における 2 番目に重要な未解決問題です。

出典

ゲーリー、マイケル R. ;ジョンソン、デビッド S. (1979)。コンピュータと扱いにくさ: NP 完全性理論ガイド。数学科学シリーズ (第 1 版)。ニューヨーク: WH フリーマンアンドカンパニー。ISBN 9780716710455. MR 0519066. OCLC 247570676.この本は古典であり、理論を展開し、多くのNP 完全問題をカタログ化しています。
Cook, SA ( 1971)。「定理証明手順の複雑さ」。議事録、第3回ACMコンピューティング理論シンポジウム、ACM、ニューヨーク。pp. 151–158。doi : 10.1145/800157.805047。
Dunne, PE「選択された NP 完全問題の注釈付きリスト」。COMP202、リバプール大学コンピュータサイエンス学部。2008年 6 月 21 日閲覧。
クレッシェンツィ、P.カン、V.ハルドーソン、M.カルピンスキー、M. ;ウーギンガー、G . 「NP 最適化問題大全」。 KTH、ストックホルム。2020年10月24日に取得。
Dahlke, K.「NP完全問題」。数学リファレンスプロジェクト。2008年6月21日閲覧。
Karlsson, R. 「講義 8: NP 完全問題」(PDF) 。スウェーデン、ルンド大学、コンピュータサイエンス学部。2009年 4 月 19 日のオリジナル(PDF)からアーカイブ。2008年 6 月 21 日に取得。
Sun, HM「NP完全性の理論」。情報セキュリティ研究所、国立清華大学コンピュータサイエンス学部、新竹市、台湾。 2009年9月2日にオリジナル（PPT）からアーカイブ。2008年6月21日に取得。
Jiang, JR「NP完全性の理論」(PPT) 。国立中央大学コンピュータサイエンスおよび情報工学部、台湾、中壢市。 2008年6月21日閲覧。
Cormen, TH ; Leiserson, CE ; Rivest, RL ; Stein, C. (2001) 「第 34 章: NP 完全性」。アルゴリズム入門(第 2 版)。MIT Press および McGraw-Hill。pp. 966–1021。ISBN 978-0-262-03293-3。
Sipser, M. (1997)。「セクション 7.4–7.5 (NP 完全性、追加の NP 完全問題)」。計算理論入門。PWS 出版。248–271 ページ。ISBN 978-0-534-94728-6。
Papadimitriou, C. (1994) 「第 9 章 (NP 完全問題)」。計算複雑性(第 1 版)。Addison Wesley。pp. 181–218。ISBN 978-0-201-53082-7。
ゲームとパズルの計算の複雑さ
テトリスは近似することさえ難しい
マインスイーパーはNP完全です！
Bern, Marshall (1990). 「平面ネットワークにおけるシュタイナーツリーの高速厳密アルゴリズム」.ネットワーク. 20 (1): 109–120. doi :10.1002/net.3230200110.。
Deĭneko, Vladimir G.; Klinz, Bettina; Woeginger, Gerhard J. (2006). 「平面グラフにおけるハミルトン閉路問題の正確なアルゴリズム」. Operations Research Letters . 34 (3): 269–274. doi :10.1016/j.orl.2005.04.013.。
Dorn, Frederic; Penninkx, Eelko; Bodlaender, Hans L .; Fomin, Fedor V. (2005)。「平面グラフ上の効率的な厳密アルゴリズム: 球面カット分岐分解の活用」。第13 回ヨーロッパアルゴリズムシンポジウム (ESA '05) 議事録。コンピュータサイエンスの講義ノート。第 3669 巻。Springer-Verlag。pp. 95–106。doi :10.1007/ 11561071_11。ISBN 978-3-540-29118-3。。
Lipton, Richard J. ; Tarjan, Robert E. (1980). 「平面セパレータ定理の応用」SIAM Journal on Computing . 9 (3): 615–627. doi :10.1137/0209046. S2CID 12961628.。

さらに読む

Scott Aaronson、「NP完全問題と物理的現実」、ACM SIGACT News、第36巻、第1号。（2005年3月）、pp.30–52。
Lance Fortnow、「P対NP問題の現状」、Commun. ACM、Vol. 52、No. 9。(2009)、pp. 78–86。

[1] たとえば、各変数にtrue を単純に代入すると、18 番目の結合(したがって完全な式)はfalse になります。 ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$

[2] Cobham, Alan (1965). 「関数の本質的な計算難度」Proc. Logic, Methodology, and Philosophy of Science II . ノースホランド。

[3] J. van Leeuwen (1998).理論計算機科学ハンドブック. Elsevier. p. 84. ISBN 978-0-262-72014-4。

[4] J. van Leeuwen (1998).理論計算機科学ハンドブック. Elsevier. p. 80. ISBN 978-0-262-72014-4。

[5] Kiersz, Andy. 「著名な数学者が数学最大の謎の一つを解いたと主張している — それは賞金100万ドルの6つの問題のうちの1つだ」。Business Insider 。 2023年4月24日閲覧。

[6] Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2010-09-06). 「頂点カバーの上限の改善」.理論計算機科学. 411 (40): 3736–3756. doi : 10.1016/j.tcs.2010.06.026 . ISSN 0304-3975.

[7] Agrawal, M. ; Allender, E.; Rudich, Steven (1998). 「回路の複雑さの削減: 同型定理とギャップ定理」. Journal of Computer and System Sciences . 57 (2): 127–143. doi : 10.1006/jcss.1998.1583 . ISSN 1090-2724.

[8] Agrawal, M. ; Allender, E.; Impagliazzo, R.; Pitassi, T. ; Rudich, Steven (2001). 「リダクションの複雑さの軽減」.計算複雑性. 10 (2): 117–138. doi :10.1007/s00037-001-8191-1. ISSN 1016-3328. S2CID 29017219.

[9] Don Knuth、Tracy Larrabee、Paul M. Roberts、「Mathematical Writing」、 Wayback Machineに 2010 年 8 月 27 日にアーカイブ§ 25、MAA Notes No. 14 、MAA、1989 ( Stanford Technical Report、1987とも)。

[10] Knuth, DF (1974). 「用語提案」SIGACT News 6 ( 1): 12–18. doi :10.1145/1811129.1811130. S2CID 45313676.

[11] 世論調査を参照、または[1] Archived 2011-06-07 at the Wayback Machine。

[12] ボール、フィリップ（2000）。「DNAコンピューターが巡回セールスマンを支援」ネイチャー。doi：10.1038/news000113-10。

[13] ベルン (1990); Deĭneko、Klinz、Woeginger (2006);ドーンら。 (2005);リプトンとタージャン (1980)。

[14] Hemaspaandra, LA; Williams, R. (2012). 「SIGACT News 複雑性理論コラム 76」. ACM SIGACT News . 43 (4): 70. doi :10.1145/2421119.2421135. S2CID 13367514.

[15] Aaronson, Scott (2010). 「BQP と多項式階層」。Schulman, Leonard J. (編)。Proceedings of the 42nd ACM Symposium on Theory of Computing、STOC 2010、ケンブリッジ、マサチューセッツ州、米国、2010 年 6 月 5 ～ 8 日。Association for Computing Machinery。pp. 141 ～ 150。arXiv : 0910.4698。doi : 10.1145 / 1806689.1806711。ISBN 978-1-4503-0050-6。

[16] タルボット、ジョン、ウェルシュ、DJA（2006）、複雑性と暗号化：入門、ケンブリッジ大学出版局、p.57、ISBN 9780521617710NP と co-NP が等しいかどうかという問題は、おそらく P 対 NP の問題に次いで、複雑性理論における 2 番目に重要な未解決問題です。