その他の便利な NP 困難問題
文字通り数千もの問題が NP 困難であると示されています。ここでは帰着を導くときに有用な NP 困難問題をいくつか紹介します。それぞれについて NP 困難性の証明の詳細を述べることはしませんが、ほとんどの問題に対する証明は Garey と Johnson による NP 完全性についての恐ろしい黒本1に載っています。ここまでに紹介した問題の全て、そしてこのリストにある問題のほとんどは、1972 年の Richard Karp (リチャード・カープ) による一つの画期的な論文で NP 困難であることが示されました2。
-
\(\textsc{PlanarCircuitSAT}\):「配線を交差させることなく平面に埋め込むことができるブール回路が与えられる。出力が \(\textsc{True}\) となるような入力が存在するか?」NP 困難性の証明は一般の回路充足問題からの帰着で行われる。帰着は一般の回路に含まれる交差するゲートをいくつかのゲートに置き換えることで平面回路に変換する。
-
\(\textsc{1-In-3SAT}\):「3CNF 式が与えられる。変数への真偽値割り当てであって全ての節がちょうど一つの \(\textsc{True}\) リテラルを持つようなものは存在するか?」NP 困難性の証明は一般的な \(\textsc{3SAT}\) からの帰着で行われる。
-
\(\textsc{NotAllEqual3SAT}\):「3CNF 式が与えられる。変数への真偽値割り当てであって全ての節が少なくとも一つの \(\textsc{True}\) リテラルと少なくとも一つの \(\textsc{False}\) リテラルを持つようなものは存在するか?」NP 困難性の証明は一般的な \(\textsc{3SAT}\) からの帰着で行われる。
-
\(\textsc{Planar3SAT}\):「与えられた平面 3CNF 式は充足可能か?」ここで 3CNF 式 \(\Phi\) が平面であるとは、頂点が \(\Phi\) の変数と節に対応し、変数と節の間に辺があるのが \(\Phi\) において節がその変数 (またはその否定) をリテラルとして持つときに限られるような二部グラフが平面グラフであることを言う。NP 困難性の証明は \(\textsc{PlanarCircuitSAT}\) からの帰着で行われる3。
-
\(\textsc{Exact3Dimenstional}\)\(\textsc{Matching}\) あるいは \(\textsc{X3M}\):「集合 \(S\) と \(S\) の要素の三つ組の集合が与えられる。三つ組の集合の部分集合であって \(S\) を重複なく被覆するようなものは存在するか?」NP 困難性の証明は \(\textsc{3SAT}\) からの帰着で行われる (3 が入っているから)。
-
\(\textsc{Partition}\):「\(n\) 個の整数の集合 \(S\) が与えられる。\(A \cup B = S\) かつ \(A \cap B = \varnothing\) を満たす \(S\) の分割 \((A, B)\) であって \[ \sum_{a \in A} a = \sum_{b \in B} b \] となるものは存在するか?」NP 困難性の証明は \(\textsc{SubsetSum}\) からの簡単な帰着で行われる。\(\textsc{Partition}\) は \(\textsc{SubsetSum}\) と同じように弱 NP 困難である。
-
\(\textsc{3Partition}\):「\(3n\) 個の整数の集合 \(S\) が与えられる。\(S\) を互いに重ならない \(n\) 個の三つ組に分け、かつ全ての三つ組の和が等しくなるようにすることは可能か?」名前は似ているが、この問題は \(\textsc{Partition}\) とは大きく異なる (名前を付けたのは私ではありませんから、許してください)。NP 困難性の証明は \(\textsc{X3M}\) からの帰着で行われる (3 が入っているから)。\(\textsc{Partition}\) と違って \(\textsc{3Partition}\) は強 NP 困難であり、入力の数字が全て \(n^{3}\) 以下であったとしても NP 困難となる。
-
\(\textsc{SetCover}\):「集合の集合 \(\pmb{S} = \lbrace S_{1}, S_{2}, \ldots, S_{m} \rbrace\) が与えられる。和集合が \(\bigcup_{i} S_{i}\) と等しくなるような最小の \(S_{i}\) の集合は何か?」この問題は \(\textsc{VertexCover}\) および \(\textsc{X3M}\) の一般化である。
-
\(\textsc{HittingSet}\):「集合の集合 \(\pmb{S} = \lbrace S_{1}, S_{2}, \ldots, S_{m} \rbrace\) が与えられる。\(\bigcup_{i} S_{i}\) の部分集合であって全ての \(S_{i}\) の要素を一つ以上持つものの大きさの最小値は何か?」この問題は \(\textsc{VertexCover}\) の一般化である。
-
\(\textsc{LongestPath}\):「辺に非負の重みの付いたグラフ \(G\) (無向でも有向でもよい) とその頂点 \(u, v\) が与えられる。\(u\) から \(v\) への最長の単純路は何か?」単純路とは同じ頂点を二度以上通らない路を言う。この問題は \(\textsc{HamiltonianPath}\) の一般化である。もちろん最短路問題ならば多項式時間で解ける。
-
\(\textsc{SteinerTree}\):「辺に重みの付いた無向グラフ \(G\) が与えられ、いくつかの頂点に印が付いている。印の付いた全ての頂点を含む \(G\) の部分木のうち最小のものは何か?」全ての頂点に印が付いているときの Steiner 木はただの最小全域木であり、印が二つの頂点だけに付いているときの Steiner 木は二つの頂点の間の最短路である。NP 困難性の証明は \(\textsc{VertexCover}\) からの帰着で行われる。
-
\(\textsc{Max2SAT}\):「各節が二つのリテラルからなる CNF のブール式が与えられる。変数の真偽値割り当ての中で \(\textsc{True}\) を一つ以上持つ節の数を最大化するものは何か?」NP 困難性の証明は \(\textsc{3SAT}\) からの帰着で行われる (3 が入っていないのに!)。\(\textsc{Max2SAT}\) を単純にした「与えられた 2CNF 式は充足可能か?」という問題は多項式時間で解ける。
-
\(\textsc{MaxCut}\):「無向グラフ \(G = (V,E)\) が与えられる。\(S \subseteq V\) の中で端点の一方だけが \(S\) に含まれる辺の数を最大化するものは何か?」 \(G\) に含まれる最大の二部グラフを見つける問題とも言える。NP 困難性の証明は \(\textsc{Max2SAT}\) からの帰着で行われる。
これまでに示した例は有用であるものの無味乾燥に感じられますが、人気のあるパズルや一人用ゲームの中にも NP 困難であることが示されているものや、一般化したものが NP 困難となることが示されているものが多くあります (NP 困難ですらないパズルは間違いなく退屈でしょう!)。あなたが知っているであろう例をいくつかあげます:
-
マインスイーパー (\(\textsc{CircuitSAT}\) からの帰着)4
-
数独 (最終的には \(\textsc{3SAT}\) からの帰着)5
-
テトリス (\(\textsc{3Partition}\) からの帰着)6
-
クロンダイク、またの名を "ソリティア" (\(\textsc{3SAT}\) からの帰着)7
-
パックマン (\(\textsc{HamiltonianCycle}\) からの帰着)8
-
スーパーマリオブラザーズ (\(\textsc{3SAT}\) からの帰着)9
-
キャンディクラッシュソーダ (\(\textsc{3SAT}\) の変種からの帰着)10
-
Threes/2048 (\(\textsc{3SAT}\) からの帰着)11
-
\(n \times n \times n\) のルービックキューブの最短解 (\(\textsc{HamiltonianCycle}\) からの帰着)12
-
クッキークリッカー (\(\textsc{Partition}\) と \(\textsc{3Partition}\) からの帰着)13
脚注の制限により、このリストは不完全です14。2019 年 6 月現在、Ultimate Paperclips, Line Rider, Twister, Cards Against Humanity を一般化したものを NP 困難だと証明した人は誰もいませんが、時間の問題でしょう。
-
Michael Garey and David Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., 1979. えぇ、この本は本当に真っ黒です。[return]
-
後にオフブロードウェイで Richard Karp and his 21 Assistants として上演され、Karp は当然
TonyTuring 賞を受賞しました。[return] -
以外にも、\(\textsc{PlanarNotAllEqual3SAT}\) は多項式時間で解けます![return]
-
Richard Kaye. Minesweeper is NP-complete. Mathematical Intelligencer 22(2):9–15, 2000. こちらも参照: Allan Scott, Ulrike Stege, and Iris van Rooij. Minesweeper may not be NP-complete but is hard nonetheless. Mathematical Intelligencer 33(4):5–17, 2011.[return]
-
Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E86-A(5):1052–1060, 2003. http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf.[return]
-
Ron Breukelaar*, Erik D. Demaine, Susan Hohenberger*, Hendrik J. Hoogeboom, Walter A. Kosters, and David Liben-Nowell*. Tetris is hard, even to approximate. International Journal of Computational Geometry and Applications 14:41–68, 2004.[return]
-
Luc Longpré and Pierre McKenzie. The complexity of Solitaire. Proceedings of the 32nd International Mathematical Foundations of Computer Science, 182–193, 2007.[return]
-
Giovanni Viglietta. Gaming is a hard job, but someone has to do it! Theory of Computing Systems, 54(4):595–621, 2014. http://giovanniviglietta.com/papers/gaming2.pdf.[return]
-
Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta. Classic Nintendo games Are (computationally) hard. Theoretical Computer Science 586:135–160, 2015. http://arxiv.org/abs/1203.1895.[return]
-
Luciano Gualà, Stefano Leucci, Emanuele Natale. Bejeweled, Candy Crush and other match-three games are (NP-)hard. Proc. 2014 IEEE Conference on Computational Intelligence and Games, 2014. http://arxiv.org/abs/1403.5830.[return]
-
Further evidence for the "rule of three". Stefan Langerman and Yushi Uno. Threes!, Fives, 1024!, and 2048 are Hard. Proc. 8th International Conference on Fun with Algorithms, 2016. https://arxiv.org/abs/1505.04274.[return]
-
Erik D. Demaine, Sarah Eisenstat, and Mikhail Rudoy. Solving the Rubik's Cube optimally is NP-complete. Proc. 35th Symposium on Theoretical Aspects of Computer Science, 2018. https://arxiv.org/abs/1706.06708.[return]
-
Erik D. Demaine, Hiro Ito, Stefan Langerman, Jayson Lynch, Mikhail Rudoy, and Kai Xiao.Cookie Clicker. Preprint, August 2018. https://arxiv.org/abs/1808.07540.[return]