その他の便利な NP 困難問題

文字通り数千もの問題が NP 困難であると示されています。ここでは帰着を導くときに有用な NP 困難問題をいくつか紹介します。それぞれについて NP 困難性の証明の詳細を述べることはしませんが、ほとんどの問題に対する証明は Garey と Johnson による NP 完全性についての恐ろしい黒本1に載っています。ここまでに紹介した問題の全て、そしてこのリストにある問題のほとんどは、1972 年の Richard Karp (リチャード・カープ) による一つの画期的な論文で NP 困難であることが示されました2

これまでに示した例は有用であるものの無味乾燥に感じられますが、人気のあるパズルや一人用ゲームの中にも NP 困難であることが示されているものや、一般化したものが NP 困難となることが示されているものが多くあります (NP 困難ですらないパズルは間違いなく退屈でしょう!)。あなたが知っているであろう例をいくつかあげます:

脚注の制限により、このリストは不完全です14。2019 年 6 月現在、Ultimate Paperclips, Line Rider, Twister, Cards Against Humanity を一般化したものを NP 困難だと証明した人は誰もいませんが、時間の問題でしょう。


  1. Michael Garey and David Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., 1979. えぇ、この本は本当に真っ黒です。[return]

  2. 後にオフブロードウェイで Richard Karp and his 21 Assistants として上演され、Karp は当然 Tony Turing 賞を受賞しました。[return]

  3. 以外にも、\(\textsc{PlanarNotAllEqual3SAT}\) は多項式時間で解けます![return]

  4. 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]

  5. 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]

  6. 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]

  7. Luc Longpré and Pierre McKenzie. The complexity of Solitaire. Proceedings of the 32nd International Mathematical Foundations of Computer Science, 182–193, 2007.[return]

  8. 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]

  9. 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]

  10. 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]

  11. 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]

  12. 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]

  13. 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]

  14. 参照: https://xkcd.com/1208/[return]

広告