NP完全問題のリスト

これは、決定問題として表現するとNP 完全となる、より一般的に知られている問題の一部のリストです。このような問題は何千も知られているため、このリストは決して包括的なものではありません。このタイプの問題の多くは、Garey & Johnson (1979) に記載されています。

グラフとハイパーグラフ

グラフは日常のアプリケーションで頻繁に使用されます。例としては、生物学的ネットワークやソーシャルネットワークが挙げられます。これらのネットワークには、数百、数千、場合によっては数十億のノードが含まれます ( FacebookやLinkedInなど)。

1-平面性^[1]
3次元マッチング^[2]^[3]^{: SP1}
帯域幅の問題^[3]^{: GT40}
二部次元^[3]^：GT18
容量付き最小全域木^[3]^：ND5
混合グラフ（有向辺と無向辺の両方を持つ）の経路調査問題（中国郵便配達問題とも呼ばれる）。グラフの辺がすべて無向かすべて有向の場合、プログラムは多項式時間で解くことができます。バリエーションには田舎の郵便配達問題があります。^[3]^{: ND25、ND27}
クリークカバー問題^[2]^[3]^{: GT17}
クリーク問題^[2]^[3]^{: GT19}
完全着色、別名無彩色数^[3]^：GT5
サイクルランク
次数制約付き全域木^[3]^：ND1
ドマティック番号^[3]^{: GT3}
支配集合、支配数^[3]^{: GT2}

NP完全な特殊なケースとしては、辺支配集合問題、すなわち線グラフの支配集合問題が挙げられる。NP完全な変種としては、連結支配集合問題と最大葉全域木問題が挙げられる。^[3]^{: ND2}

フィードバック頂点集合^[2]^[3]^{: GT7}
フィードバックアークセット^[2]^[3]^{: GT8}
グラフカラーリング^[2]^[3]^{: GT4}
グラフ準同型問題^[3]^{: GT52}
グラフを特定のタイプ（三角形、同型サブグラフ、ハミルトンサブグラフ、フォレスト、完全マッチング）のサブグラフに分割することはNP完全であることが知られている。クリークへの分割は、与えられたグラフの補グラフに色を付けるのと同じ問題である。関連する問題として、部分間の辺の数に関して最適な分割を見つけることが挙げられる。^[3]^{: GT11、GT12、GT13、GT14、GT15、GT16、ND14}
有向グラフのグランディ数。 ^[3]^{: GT56}
ハミルトン完成^[3]^{: GT34}
ハミルトン経路問題、有向および無向。^[2]^[3]^{: GT37, GT38, GT39}
誘導部分グラフ同型性問題
グラフ交点数^[3]^{: GT59}
最長経路問題^[3]^{: ND29}
最大二部グラフまたは（特に重み付き辺を持つ）最大カット。^[2]^[3]^{：GT25、ND16}
最大共通部分グラフ同型性問題^[3]^{: GT49}
最大独立集合^[3]^：GT20
最大誘導経路^[3]^：GT23
最小最大独立集合、別名最小独立支配集合^[4]

NP完全な特殊なケースには、最小最大マッチング問題^[3]^：GT10があり、これは本質的にエッジ支配集合問題（上記参照）に等しい。

グラフのメトリック次元^[3]^：GT61
メトリックk中心
最小次数全域木
最小kカット
最小k全域木
マイナーテスト（入力グラフにマイナーとして入力グラフが含まれているかどうかをチェックする）; 位相マイナーでも同様である $G$ $H$
シュタイナー木、またはグラフの頂点のサブセットに対する最小全域木。 ^[2]（グラフ全体の最小全域木は多項式時間で解くことができます。）
モジュール性の最大化^[5]
単色三角形^[3]^{: GT6}
パス幅[ ^6]または、同等に、間隔の厚さ、および頂点の分離数^[7]
ランクの色分け
k-中国の郵便配達員
最短総経路長全域木^[3]^：ND3
傾斜2テスト^[8]
文字列グラフの認識^[9]
部分グラフ同型性問題^[3]^{: GT48}
ツリー幅^[6]
木がユークリッド最小全域木として表現できるかどうかをテストする
頂点カバー^[2]^[3]^{: GT1}

数理計画法

3分割問題^[3]^：SP15
ビンパッキング問題^[3]^{: SR1}
ボトルネック巡回セールスマン^[3]^：ND24
収容能力のない施設の配置問題
フローショップスケジューリング問題
一般化割り当て問題
整数計画法。変数が0か1であることが求められる変種はゼロワン線形計画法と呼ばれ、他のいくつかの変種もNP完全である^[2]^[3]^{: MP1}
ジョブショップスケジューリングに関連するいくつかの問題
ナップサック問題、二次ナップサック問題、およびいくつかの変種^[2]^[3]^{: MP9}
マルチプロセッサスケジューリングに関連するいくつかの問題
数値3次元マッチング^[3]^：SP16
オープンショップのスケジュール
パーティション問題^[2]^[3]^{: SP12}
二次割り当て問題^[3]^{: ND43}
二次計画法（場合によっては NP 困難、凸の場合は P）
部分集合和問題^[3]^{: SP13}
巡回セールスマン問題のバリエーション。グラフの問題は、辺の長さが整数であると仮定すればNP完全である。平面上の点の問題は、離散化ユークリッド距離と直線距離でNP完全である。この問題は、（離散化されていない）ユークリッド距離ではNP困難であることが知られている。^[3]^{: ND22, ND23}

形式言語と文字列処理

最も近い文字列^[10]
複数のシーケンス上の最長共通部分列問題^[3]^{: SR10}
ポスト対応問題の有界変種^[3]^：SR11
複数のシーケンスにわたる最短共通スーパーシーケンス^[3]^{: SR8}
文字列訂正問題の拡張^[11]^[3]^{: SR8}

ゲームとパズル

バッグ（コラール）^[12]
戦艦
Bulls and Cows 、 Master Mindとして販売: 特定の最適化問題がありますが、ゲーム自体ではありません。
エッジマッチングパズル
フィロミノ^[13]
（一般化）フリーセル^[14]
広井碁石
橋をかけろ^[15]
ヘヤワケ^[16]
（一般化）インスタント・インサニティ^[3]^：GP15
カックロ（クロスサムズ）^[17]
キングダムミノ^[18]
黒枡（別名：黒床）^[19]
レーザータンク^[20]
レミングス（多項式時間制限付き）^[21]
ライトアップ^[22]
麻雀ソリティア（牌の下を見る）
ましゅ^[23]
マインスイーパーの一貫性問題^[24] (ただし、Scott、Stege、van Rooij ^[25]を参照)
ノノグラム
ナンバーリンク
ぬりかべ^[26]
（一般化）パンデミック^[27]
ペグソリティア
n-クイーンの完成
$N \times N \times N$ ルービックキューブの最適解^[28]
セイムゲーム
シャカシャカ
さまざまなグリッド上のスリザーリンク^[29]^[30]^[31]
（一般化）数独^[29]^[32]
畳張り
天体ショー
テトリスに関連する問題^[33]
言葉による算数

他の

バース割り当て問題^[34]
中間性
最適なビットコインブロックの組み立て。^[35]
ブール充足可能性問題(SAT) ^[2]^[3]^{: LO1} NP完全でもある多くのバリエーションがあります。重要なバリエーションは、各節がちょうど3つのリテラルを持つ場合 (3SAT) です。これは、他の多くのNP完全性の結果の証明に使用されているためです。^[3]^{: p. 48}
回路充足可能性問題
結合ブールクエリ^[3]^{: SR31}
循環順序付け^[36]
完全被覆問題。3-集合に対してNP完全のまま。2-集合に対しては多項式時間で解ける（これはマッチングである）。^[2]^[3]^{: SP2}
ハートリー・フォック問題の大域的最小解を求める^[37]
上方平面性試験^[8]
病院と入居者のカップル問題
ノット属^[38]
ラテン方陣完成（部分的に埋められた正方形が完成できるかどうかを判断する問題）
最大2-充足可能性^[3]^：LO5
最大体積サブマトリックス– より大きなマトリックスから最良の条件付きサブセットを選択する問題。この種の問題は、ランクを明らかにするQR分解とD最適実験設計に関連しています。^[39] $m\times n$
数列の最小加算連鎖。^[40]個々の数に対する最小加算連鎖の複雑さは不明である。^[41]
様相論理 S5 - 満足可能性
文字列のパンケーキソート距離問題^[42]
2変数2次多項式の整数上の可解性。[ ^43]正の整数が与えられたとき、 $\textstyle A、B、C$ $x,y$ $Ax^{2}+By-C=0$
同じ論文^[43]によれば、任意の合成係数を持つ有界モジュラー平方根の存在。正の整数が与えられたとき、となる整数の存在を判定する。の素因数分解が提供されても、問題はNP完全のままである。 $\textstyle A,B,C\geq 0$ $x\in [0,C]$ $x^{2}\equiv A{\bmod {B}}$ $B$
データベース履歴の直列化可能性^[3]^{: SR33}
セットカバー（「最小カバー」問題とも呼ばれる）。これは、接続行列を転置することで、ヒットセット問題と同等になります。^[2]^[3]^{: SP5、SP8}
セットパッキング^[2]^[3]^{: SP3}
集合分割問題^[3]^：SP4
加重完了時間を最小化するスケジュール
ブロックソート^[44]（ブロック移動によるソート）
スパース近似
シュタイナー木問題のバリエーション。特に、離散化ユークリッド計量、直線計量の場合。この問題は、（離散化されていない）ユークリッド計量ではNP困難であることが知られています。^[3]^{: ND13}
3次元イジングモデル^[45]

参照

注記

^ グリゴリエフ＆ボドランダー（2007年）。
^ abcdefghijklmnopq カープ (1972)
^ abcdefghijklmnopqrstu vwxyz aa ab ac ad ae af ag ah ai aj ak al am an ao ap aq ar as at au av aw ax ay az ba bb bc bd be Garey & Johnson (1979)
^ 最小独立支配集合
^ Brandes, Ulrik ; Delling, Daniel; Gaertler, Marco; Görke, Robert; Hoefer, Martin; Nikoloski, Zoran; Wagner, Dorothea (2006)、モジュール性の最大化は難しい、arXiv : physics/0608255、Bibcode :2006physics...8255B
^ ab アーンボルグ、コルニール、プロスクロフスキー (1987)
^ 柏原・藤澤 (1979);大槻ら。 (1979);レンガウアー (1981)。
^ ab Garg, Ashim; Tamassia, Roberto (1995). 「上向きおよび直線平面性テストの計算複雑性について」.コンピュータサイエンスの講義ノート. Vol. 894/1995. pp. 286–297. doi :10.1007/3-540-58950-3_384. ISBN 978-3-540-58950-1。
^ Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel (2003年9月). 「NPにおける文字列グラフの認識」. Journal of Computer and System Sciences . 67 (2): 365–380. doi : 10.1016/S0022-0000(03)00045-X .
^ Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003)、「文字列選択問題の区別」、Information and Computation、185 (1): 41–55、doi : 10.1016/S0890-5401(03)00057-9、MR 1994748
^ Wagner, Robert A. (1975 年 5 月)。「拡張された文字列から文字列への訂正問題の複雑さについて」。第 7 回 ACM コンピューティング理論シンポジウム議事録 - STOC '75 。pp . 218–223。doi :10.1145/ 800116.803771。ISBN 9781450374194. S2CID 18705107。
^ フリードマン、エリック。「コラルパズルはNP完全である」（PDF）。 2021年8月17日閲覧。
^ 矢藤孝己 (2003). 「別の解を求めることの複雑性と完全性およびパズルへの応用」CiteSeerX 10.1.1.103.8380 .
^ Malte Helmert、「計画における標準ベンチマークドメインの複雑性の結果」、人工知能 143(2):219-262、2003年。
^ 「HASHIWOKAKEROはNP完全である」。
^ ホルツァー＆ルーップ（2007）
^ 瀬田貴弘 (2002年2月5日). 「パズルの複雑性、クロスサム、およびそれらの別の解決問題 (ASP)」(PDF) 。2018年11月18日閲覧。
^ Nguyen, Viet-Ha; Perrot, Kévin; Vallet, Mathieu (2020年6月24日). 「ゲームKingdominoTMのNP完全性」.理論計算機科学. 822 : 23–35. doi : 10.1016/j.tcs.2020.04.007 . ISSN 0304-3975. S2CID 218552723.
^ Kölker, Jonas (2012). 「KurodokoはNP完全である」(PDF) . Journal of Information Processing . 20 (3): 694–706. doi :10.2197/ipsjjip.20.694. S2CID 46486962. 2020年2月12日時点のオリジナル(PDF)からアーカイブ。
^ Alexandersson, Per; Restadh, Petter (2020). 「LaserTank は NP 完全です」。コンピュータと情報科学の数学的側面。コンピュータサイエンスの講義ノート。 Vol. 11989。 Springer International Publishing。 pp. 333–338。arXiv : 1908.05966。doi :10.1007/978-3-030-43120-4_26。ISBN 978-3-030-43119-8. S2CID 201058355。
^ Cormode, Graham (2004). レミングゲームの難しさ、あるいは、ああ、NP完全性の証明がさらに増えた(PDF)。
^ ライトアップはNP完了です
^ Friedman, Erich (2012年3月27日). 「Pearl Puzzles are NP-complete」. 2012年2月4日時点のオリジナルよりアーカイブ。
^ ケイ（2000）
^ Allan Scott、Ulrike Stege、Iris van Rooij、「マインスイーパはNP完全ではないかもしれないが、それでも難しい」、The Mathematical Intelligencer 33 :4 (2011)、pp.5–17。
^ Holzer, Markus; Klein, Andreas; Kutrib, Martin; Ruepp, Oliver (2011). 「NURIKABE の計算複雑性」. Fundamenta Informaticae . 110 (1–4): 159–174. doi :10.3233/FI-2011-534.
^ 中井健一郎;竹永、安彦（2012）。「NP-パンデミックの完全性」。情報処理ジャーナル。20 (3): 723–726。土井：10.2197/ipsjjip.20.723。ISSN 1882-6652。
^ Demaine, Erik; Eisenstat, Sarah; Rudoy, Mikhail (2018).ルービックキューブを最適に解くことはNP完全である。第35回コンピュータサイエンスの理論的側面に関するシンポジウム (STACS 2018). doi : 10.4230/LIPIcs.STACS.2018.24。
^ ab 佐藤隆之; 瀬田隆弘 (1987). 別解探索の複雑性と完全性およびパズルへの応用(PDF) . 国際アルゴリズムシンポジウム (SIGAL 1987).
^貫井、上島（2007 年3月）。「複数のグリッド上のスリザーリンクパズルのASP完全性」。Ipsj Sig Notes。2007（23）：129–136。
^ Kölker, Jonas (2012). 「選択されたスリザーリンクバリアントはNP完全である」.情報処理ジャーナル. 20 (3): 709–712. doi : 10.2197/ipsjjip.20.709 .
^ NP完全パズルの調査、第23章; Graham Kendall、Andrew Parkes、Kristian Spoerer; 2008年3月。(icga2008.pdf)
^ Demaine, Eric D.; Hohenberger, Susan; Liben-Nowell, David (2003 年 7 月 25 ～ 28 日)。Tetris は近似値を求めるのも難しい(PDF)。第 9 回国際コンピューティングおよび組合せ論会議 (COCOON 2003) の議事録。ビッグスカイ、モンタナ州。
^ リム、アンドリュー（1998）、「バース計画問題」、オペレーションズ・リサーチ・レター、22（2–3）：105–110、doi：10.1016/S0167-6377（98）00010-8、MR 1653377
^ J. Bonneau、「ビットコインマイニングはNP困難」
^ Galil, Zvi; Megiddo, Nimrod (1977年10月). 「巡回順序はNP完全である」.理論計算機科学. 5 (2): 179–182. doi : 10.1016/0304-3975(77)90005-6 .
^ Whitfield, James Daniel; Love, Peter John; Aspuru-Guzik, Alán (2013). 「電子構造における計算複雑性」. Phys. Chem. Chem. Phys . 15 (2): 397–411. arXiv : 1208.3334 . Bibcode :2013PCCP...15..397W. doi :10.1039/C2CP42695A. PMID 23172634. S2CID 12351374.
^ Agol, Ian ; Hass, Joel ; Thurston, William (2002 年 5 月 19 日)。「3 次元の結び目の種数は NP 完全である」。第34 回 ACM コンピューティング理論シンポジウムの議事録。STOC '02。ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery。pp. 761–766。arXiv : math /0205057。doi :10.1145/ 509907.510016。ISBN 978-1-58113-495-7. S2CID 10401375。
^ Çivril, Ali; Magdon-Ismail, Malik (2009)、「行列の最大体積部分行列の選択と関連する問題」(PDF)、Theoretical Computer Science、410 (47–49): 4801–4811、doi :10.1016/j.tcs.2009.06.018、MR 2583677、 2015年2月3日のオリジナル(PDF)からアーカイブ
^ ピーター・ダウニー、ベントン・レオン、ラヴィ・セティ「加算チェーンによるシーケンスの計算」SIAM J. Comput.、10(3)、638–646、1981
^ DJ Bernstein、「ピピンガーの指数アルゴリズム」（草稿）
^ Hurkens, C.; Iersel, LV; Keijsper, J.; Kelk, S.; Stougie, L.; Tromp, J. (2007). 「2進数および3進数文字列のプレフィックス反転」SIAM J. Discrete Math . 21 (3): 592–611. arXiv : math/0602456 . doi :10.1137/060664252.
^ ab Manders, Kenneth; Adleman, Leonard ( 1976). 「2次多項式のNP完全決定問題」。第8回ACMコンピューティング理論シンポジウム議事録 - STOC '76。pp. 23–29。doi :10.1145 / 800113.803627。ISBN 9781450374149.S2CID 18885088 。
^ Bein, WW; Larmore, LL; Latifi, S.; Sudborough, IH (2002 年 1 月 1 日)。「ブロックソートは難しい」。並列アーキテクチャ、アルゴリズム、ネットワークに関する国際シンポジウムの議事録。I-SPAN'02。pp . 307–312。doi : 10.1109 /ISPAN.2002.1004305。ISBN 978-0-7695-1579-3.S2CID 32222403 。
^ Barry Arthur Cipra、「イジングモデルはNP完全である」、SIAM News、第33巻、第6号。

参考文献

一般的な

ゲーリー、マイケル 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。
Karp, Richard M. (1972)。「組み合わせ問題における縮約可能性」。Miller, Raymond E.、Thatcher, James W. (編)。『コンピュータ計算の複雑性』。Plenum。pp. 85–103。
Dunne, PE「選択された NP 完全問題の注釈付きリスト」。COMP202、リバプール大学コンピュータサイエンス学部。2008年6 月 21 日閲覧。
クレッシェンツィ、P.カン、V.ハルドーソン、M.カルピンスキー、M. ;ウーギンガー、G . 「NP 最適化問題大全」。 KTH NADA、ストックホルム。2008 年6 月 21 日に取得。
Dahlke, K.「NP完全問題」。数学リファレンスプロジェクト。 2008年6月21日閲覧。

具体的な問題

Friedman, E (2002). 「パールパズルはNP完全」。フロリダ州デランド、ステットソン大学。2006年9月4日時点のオリジナルよりアーカイブ。 2008年6月21日閲覧。
Grigoriev, A; Bodlaender, HL (2007). 「エッジあたりの交差が少ない埋め込み可能なグラフのアルゴリズム」. Algorithmica . 49 (1): 1–11. CiteSeerX 10.1.1.61.3576 . doi :10.1007/s00453-007-0010-x. MR 2344391. S2CID 8174422.
Hartung, S; Nichterlein, A (2012). 「有向非巡回グラフによる次数列の実現の NP 困難性と固定パラメータの扱いやすさ」。How the World Computes 。Lecture Notes in Computer Science。Vol. 7318。Springer 、ベルリン、ハイデルベルク。pp . 283–292。CiteSeerX 10.1.1.377.2077。doi : 10.1007 /978-3-642-30870-3_29。ISBN 978-3-642-30869-7. S2CID 6112925。
Holzer, Markus; Ruepp, Oliver (2007)。「インテリアデザインの悩み - ゲーム Heyawake の複雑性分析」(PDF)。議事録、第 4 回アルゴリズムを楽しむ国際会議、LNCS 4475。Springer、ベルリン/ハイデルベルク。pp. 198–212。doi :10.1007 / 978-3-540-72914-3_18。ISBN 978-3-540-72913-6。
ケイ、リチャード (2000)。「マインスイーパはNP完全である」。数学インテリジェンサー。22 (2): 9–15。doi : 10.1007/BF03025367。S2CID 122435790 。さらに詳しい情報は、Richard Kaye の Minesweeper ページでオンラインで入手できます。
柏原孝文; 藤沢孝文 (1979) 「与えられたグラフをサブグラフとして含む最小クリーク数区間グラフを見つける問題の NP 完全性」議事録.回路とシステムに関する国際シンポジウム. pp. 657–660。
大月達夫; 森創; クーアーネスト S.; 柏原俊信; 藤沢敏夫 (1979). 「1 次元論理ゲート割り当てと区間グラフ」. IEEE Transactions on Circuits and Systems . 26 (9): 675–684. doi :10.1109/TCS.1979.1084695.
Lengauer, Thomas (1981). 「白黒の小石とグラフの分離」. Acta Informatica . 16 (4): 465–475. doi :10.1007/BF00264496. S2CID 19415148.
Arnborg, Stefan; Corneil, Derek G .; Proskurowski, Andrzej (1987). 「 kツリーにおける埋め込みの検出の複雑さ」 SIAM Journal on Algebraic and Discrete Methods . 8 (2): 277–284. doi :10.1137/0608024.
Cormode, Graham (2004)。「レミングゲームの難しさ、あるいは、ああ、NP完全性の証明がさらに増えた」。アルゴリズムを楽しむための第3回国際会議 (FUN 2004) の議事録。65～76 ページ。

外部リンク

NP最適化問題の概要
NP完全問題のグラフ

[FOOTNOTEGrigorievBodlaender2007-1] グリゴリエフ＆ボドランダー（2007年）。

[karp-2] q カープ (1972)

[gj1979-3] qrstu vwxyz aa ab ac ad ae af ag ah ai aj ak al am an ao ap aq ar as at au av aw ax ay az ba bb bc bd be Garey & Johnson (1979)

[4] 最小独立支配集合

[5] Brandes, Ulrik ; Delling, Daniel; Gaertler, Marco; Görke, Robert; Hoefer, Martin; Nikoloski, Zoran; Wagner, Dorothea (2006)、モジュール性の最大化は難しい、arXiv : physics/0608255、Bibcode :2006physics...8255B

[acp1987-6] アーンボルグ、コルニール、プロスクロフスキー (1987)

[7] 柏原・藤澤 (1979);大槻ら。 (1979);レンガウアー (1981)。

[Comp2Planar-8] Garg, Ashim; Tamassia, Roberto (1995). 「上向きおよび直線平面性テストの計算複雑性について」.コンピュータサイエンスの講義ノート. Vol. 894/1995. pp. 286–297. doi :10.1007/3-540-58950-3_384. ISBN 978-3-540-58950-1。

[9] Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel (2003年9月). 「NPにおける文字列グラフの認識」. Journal of Computer and System Sciences . 67 (2): 365–380. doi : 10.1016/S0022-0000(03)00045-X .

[10] Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003)、「文字列選択問題の区別」、Information and Computation、185 (1): 41–55、doi : 10.1016/S0890-5401(03)00057-9、MR 1994748

[11] Wagner, Robert A. (1975 年 5 月)。「拡張された文字列から文字列への訂正問題の複雑さについて」。第 7 回 ACM コンピューティング理論シンポジウム議事録 - STOC '75 。pp . 218–223。doi :10.1145/ 800116.803771。ISBN 9781450374194. S2CID 18705107。

[12] フリードマン、エリック。「コラルパズルはNP完全である」（PDF）。 2021年8月17日閲覧。

[13] 矢藤孝己 (2003). 「別の解を求めることの複雑性と完全性およびパズルへの応用」CiteSeerX 10.1.1.103.8380 .

[14] Malte Helmert、「計画における標準ベンチマークドメインの複雑性の結果」、人工知能 143(2):219-262、2003年。

[15] 「HASHIWOKAKEROはNP完全である」。

[Holzer-Ruepp07-16] ホルツァー＆ルーップ（2007）

[17] 瀬田貴弘 (2002年2月5日). 「パズルの複雑性、クロスサム、およびそれらの別の解決問題 (ASP)」(PDF) 。2018年11月18日閲覧。

[18] Nguyen, Viet-Ha; Perrot, Kévin; Vallet, Mathieu (2020年6月24日). 「ゲームKingdominoTMのNP完全性」.理論計算機科学. 822 : 23–35. doi : 10.1016/j.tcs.2020.04.007 . ISSN 0304-3975. S2CID 218552723.

[Kölker12b-19] Kölker, Jonas (2012). 「KurodokoはNP完全である」(PDF) . Journal of Information Processing . 20 (3): 694–706. doi :10.2197/ipsjjip.20.694. S2CID 46486962. 2020年2月12日時点のオリジナル(PDF)からアーカイブ。

[20] Alexandersson, Per; Restadh, Petter (2020). 「LaserTank は NP 完全です」。コンピュータと情報科学の数学的側面。コンピュータサイエンスの講義ノート。 Vol. 11989。 Springer International Publishing。 pp. 333–338。arXiv : 1908.05966。doi :10.1007/978-3-030-43120-4_26。ISBN 978-3-030-43119-8. S2CID 201058355。

[Cormode04-21] Cormode, Graham (2004). レミングゲームの難しさ、あるいは、ああ、NP完全性の証明がさらに増えた(PDF)。

[22] ライトアップはNP完了です

[Friedman-23] Friedman, Erich (2012年3月27日). 「Pearl Puzzles are NP-complete」. 2012年2月4日時点のオリジナルよりアーカイブ。

[24] ケイ（2000）

[25] Allan Scott、Ulrike Stege、Iris van Rooij、「マインスイーパはNP完全ではないかもしれないが、それでも難しい」、The Mathematical Intelligencer 33 :4 (2011)、pp.5–17。

[26] Holzer, Markus; Klein, Andreas; Kutrib, Martin; Ruepp, Oliver (2011). 「NURIKABE の計算複雑性」. Fundamenta Informaticae . 110 (1–4): 159–174. doi :10.3233/FI-2011-534.

[27] 中井健一郎;竹永、安彦（2012）。「NP-パンデミックの完全性」。情報処理ジャーナル。20 (3): 723–726。土井：10.2197/ipsjjip.20.723。ISSN 1882-6652。

[28] Demaine, Erik; Eisenstat, Sarah; Rudoy, Mikhail (2018).ルービックキューブを最適に解くことはNP完全である。第35回コンピュータサイエンスの理論的側面に関するシンポジウム (STACS 2018). doi : 10.4230/LIPIcs.STACS.2018.24。

[sigal87-29] 佐藤隆之; 瀬田隆弘 (1987). 別解探索の複雑性と完全性およびパズルへの応用(PDF) . 国際アルゴリズムシンポジウム (SIGAL 1987).

[NU07-30] ^貫井、上島（2007 年3月）。「複数のグリッド上のスリザーリンクパズルのASP完全性」。Ipsj Sig Notes。2007（23）：129–136。

[Kölker12c-31] Kölker, Jonas (2012). 「選択されたスリザーリンクバリアントはNP完全である」.情報処理ジャーナル. 20 (3): 709–712. doi : 10.2197/ipsjjip.20.709 .

[32] NP完全パズルの調査、第23章; Graham Kendall、Andrew Parkes、Kristian Spoerer; 2008年3月。(icga2008.pdf)

[33] Demaine, Eric D.; Hohenberger, Susan; Liben-Nowell, David (2003 年 7 月 25 ～ 28 日)。Tetris は近似値を求めるのも難しい(PDF)。第 9 回国際コンピューティングおよび組合せ論会議 (COCOON 2003) の議事録。ビッグスカイ、モンタナ州。

[34] リム、アンドリュー（1998）、「バース計画問題」、オペレーションズ・リサーチ・レター、22（2–3）：105–110、doi：10.1016/S0167-6377（98）00010-8、MR 1653377

[35] J. Bonneau、「ビットコインマイニングはNP困難」

[36] Galil, Zvi; Megiddo, Nimrod (1977年10月). 「巡回順序はNP完全である」.理論計算機科学. 5 (2): 179–182. doi : 10.1016/0304-3975(77)90005-6 .

[37] Whitfield, James Daniel; Love, Peter John; Aspuru-Guzik, Alán (2013). 「電子構造における計算複雑性」. Phys. Chem. Chem. Phys . 15 (2): 397–411. arXiv : 1208.3334 . Bibcode :2013PCCP...15..397W. doi :10.1039/C2CP42695A. PMID 23172634. S2CID 12351374.

[38] Agol, Ian ; Hass, Joel ; Thurston, William (2002 年 5 月 19 日)。「3 次元の結び目の種数は NP 完全である」。第34 回 ACM コンピューティング理論シンポジウムの議事録。STOC '02。ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery。pp. 761–766。arXiv : math /0205057。doi :10.1145/ 509907.510016。ISBN 978-1-58113-495-7. S2CID 10401375。

[39] Çivril, Ali; Magdon-Ismail, Malik (2009)、「行列の最大体積部分行列の選択と関連する問題」(PDF)、Theoretical Computer Science、410 (47–49): 4801–4811、doi :10.1016/j.tcs.2009.06.018、MR 2583677、 2015年2月3日のオリジナル(PDF)からアーカイブ

[40] ピーター・ダウニー、ベントン・レオン、ラヴィ・セティ「加算チェーンによるシーケンスの計算」SIAM J. Comput.、10(3)、638–646、1981

[41] DJ Bernstein、「ピピンガーの指数アルゴリズム」（草稿）

[42] Hurkens, C.; Iersel, LV; Keijsper, J.; Kelk, S.; Stougie, L.; Tromp, J. (2007). 「2進数および3進数文字列のプレフィックス反転」SIAM J. Discrete Math . 21 (3): 592–611. arXiv : math/0602456 . doi :10.1137/060664252.

[NP-complete_decision_problems_for_Quadratic_Polynomials-43] Manders, Kenneth; Adleman, Leonard ( 1976). 「2次多項式のNP完全決定問題」。第8回ACMコンピューティング理論シンポジウム議事録 - STOC '76。pp. 23–29。doi :10.1145 / 800113.803627。ISBN 9781450374149.S2CID 18885088 。

[44] Bein, WW; Larmore, LL; Latifi, S.; Sudborough, IH (2002 年 1 月 1 日)。「ブロックソートは難しい」。並列アーキテクチャ、アルゴリズム、ネットワークに関する国際シンポジウムの議事録。I-SPAN'02。pp . 307–312。doi : 10.1109 /ISPAN.2002.1004305。ISBN 978-0-7695-1579-3.S2CID 32222403 。

[45] Barry Arthur Cipra、「イジングモデルはNP完全である」、SIAM News、第33巻、第6号。

グラフとハイパーグラフ

数理計画法

形式言語と文字列処理

ゲームとパズル

他の

参照

注記

参考文献

外部リンク

関連するトピック

これは、決定問題

NP 完全と

グラフは

Facebook