ベータ版リリース。Problem Forgeは新しいサイトで、招待制で公開しています。ベータテスト期間は2026-11-30までです。正式オープンは2026-12-01 00:00 UTCです。不具合が起きることがあり、そのときはランキングを修正することがあります。一部の段の難しさが正しくないことがあります。ベータ版の間は賞品はなく、懸賞金も始まっていません。ベータ版が終わっても、アカウントと進み具合はそのまま残ります。うまくいっていることも、問題があることも、ぜひ教えてください：admin@problemforge.com。

参考文献

10個の問題についてさらに読むための資料と、登るのに役立つツールです。まずは Wikipedia から始めてください。下の論文と本は、古典的な文献です。

背景：P、NP、NP 完全性

  • Wikipedia：P versus NP problem、 NP-completeness、 Cook–Levin theorem。
  • Clay Mathematics Institute、P vs NP。 7つのミレニアム懸賞問題の1つです。
  • Stephen A. Cook, "The complexity of theorem-proving procedures", Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC '71), 1971, pp. 151–158. doi:10.1145/800157.805047
  • Richard M. Karp, "Reducibility among combinatorial problems", in R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, 1972, pp. 85–103. doi:10.1007/978-1-4684-2001-2_9
  • Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. ISBN 0-7167-1045-5。NP 完全な問題の標準的な一覧です。
  • Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2013. ISBN 978-1-133-18779-0。第7章で P、NP、NP 完全性を紹介しています。
  • Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. doi:10.1017/CBO9780511804090

ブール充足可能性問題 (SAT)

  • Wikipedia：Boolean satisfiability problem、 SAT solver。
  • 古典：Cook 1971（上記）。最初の NP 完全性の証明です。解き方については、Martin Davis and Hilary Putnam, "A computing procedure for quantification theory", Journal of the ACM 7(3), 1960, pp. 201–215, doi:10.1145/321033.321034、 および Martin Davis, George Logemann and Donald Loveland, "A machine program for theorem-proving", Communications of the ACM 5(7), 1962, pp. 394–397, doi:10.1145/368273.368557 （DPLL。現代のどのソルバーにも使われている方法です）。
  • 概説：Armin Biere, Marijn Heule, Hans van Maaren and Toby Walsh (eds.), Handbook of Satisfiability, 2nd ed., IOS Press, 2021. doi:10.3233/FAIA336

3-SAT

  • Wikipedia：3-satisfiability （SAT の記事の中の1節です）。
  • 古典：Uwe Schöning, "A probabilistic algorithm for k-SAT and constraint satisfaction problems", 40th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 1999, pp. 410–414, doi:10.1109/SFFCS.1999.814612。 論文誌版は Algorithmica 32(4), 2002, pp. 615–623, doi:10.1007/s00453-001-0094-7。 ランダムに動く単純な方法です。3-SAT では、すべての場合を試すより速く解けます。
  • 教科書：Donald E. Knuth, The Art of Computer Programming, Volume 4B: Combinatorial Algorithms, Part 2, Addison-Wesley, 2023, section 7.2.2.2 (Satisfiability). ISBN 0-201-03806-4.

独立集合

クリーク

  • Wikipedia：Clique problem。
  • 古典：Coen Bron and Joep Kerbosch, "Algorithm 457: finding all cliques of an undirected graph", Communications of the ACM 16(9), 1973, pp. 575–577. doi:10.1145/362342.362367
  • 概説：Qinghua Wu and Jin-Kao Hao, "A review on algorithms for maximum clique problems", European Journal of Operational Research 242(3), 2015, pp. 693–709. doi:10.1016/j.ejor.2014.09.064

頂点被覆

  • Wikipedia：Vertex cover。
  • 古典：G. L. Nemhauser and L. E. Trotter, "Vertex packings: structural properties and algorithms", Mathematical Programming 8(1), 1975, pp. 232–248. doi:10.1007/BF01580444 ほかに：Jianer Chen, Iyad A. Kanj and Ge Xia, "Improved upper bounds for vertex cover", Theoretical Computer Science 411(40–42), 2010, pp. 3736–3756. doi:10.1016/j.tcs.2010.06.026
  • 教科書：Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk and Saket Saurabh, Parameterized Algorithms, Springer, 2015. doi:10.1007/978-3-319-21275-3

グラフの 3 彩色

  • Wikipedia：Graph coloring。
  • 古典：Daniel Brélaz, "New methods to color the vertices of a graph", Communications of the ACM 22(4), 1979, pp. 251–256 （DSatur 法）。 doi:10.1145/359094.359101 ほかに：Richard Beigel and David Eppstein, "3-coloring in time O(1.3289^n)", Journal of Algorithms 54(2), 2005, pp. 168–204. doi:10.1016/j.jalgor.2004.06.008
  • 教科書：R. M. R. Lewis, Guide to Graph Colouring: Algorithms and Applications, 2nd ed., Springer, 2021. doi:10.1007/978-3-030-81054-2

ハミルトン閉路

  • Wikipedia：Hamiltonian path problem、 Hamiltonian path。
  • 古典：Michael Held and Richard M. Karp, "A dynamic programming approach to sequencing problems", Journal of the Society for Industrial and Applied Mathematics 10(1), 1962, pp. 196–210, doi:10.1137/0110015、および Richard Bellman, "Dynamic programming treatment of the travelling salesman problem", Journal of the ACM 9(1), 1962, pp. 61–63, doi:10.1145/321105.321111。 現代の研究：Andreas Björklund, "Determinant sums for undirected Hamiltonicity", SIAM Journal on Computing 43(1), 2014, pp. 280–299. doi:10.1137/110839229
  • 概説：Ronald J. Gould, "Advances on the Hamiltonian problem – a survey", Graphs and Combinatorics 19(1), 2003, pp. 7–52. doi:10.1007/s00373-002-0492-x
  • 難しいインスタンス：Joeri Sleegers and Daan van den Berg, "The hardest Hamiltonian cycle problem instances: the plateau of yes and the cliff of no", SN Computer Science 3, article 372, 2022. オープンアクセス。 doi:10.1007/s42979-022-01256-0

巡回セールスマン問題 (TSP)

  • Wikipedia：Travelling salesman problem。
  • 古典：G. Dantzig, R. Fulkerson and S. Johnson, "Solution of a large-scale traveling-salesman problem", Journal of the Operations Research Society of America 2(4), 1954, pp. 393–410, doi:10.1287/opre.2.4.393、 および S. Lin and B. W. Kernighan, "An effective heuristic algorithm for the traveling-salesman problem", Operations Research 21(2), 1973, pp. 498–516, doi:10.1287/opre.21.2.498。 Held and Karp 1962（上記）は、厳密に解く動的計画法の古典です。
  • 本：David L. Applegate, Robert E. Bixby, Vašek Chvátal and William J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2006. ISBN 978-0-691-12993-8.

0-1 整数計画問題

3 要素集合による完全被覆 (X3C)

  • Wikipedia：Exact cover （3 要素集合による完全被覆は、どの集合も要素を3つ持つ場合です）、Knuth's Algorithm X、 Dancing links。
  • 古典：Donald E. Knuth, "Dancing links", in Millennial Perspectives in Computer Science, 2000, pp. 187–214. arXiv:cs/0011047 この問題は、Garey and Johnson 1979（上記）に [SP2] として載っています。
  • 教科書：Donald E. Knuth, The Art of Computer Programming, Volume 4B, Addison-Wesley, 2023, section 7.2.2.1 (Dancing links). ISBN 0-201-03806-4.

ソルバーとツール

ライセンスは、各プロジェクトが示しているとおりに書いています。 「学術目的」とあるものは、それ以外の使い方には許可が必要な場合があります。

SAT

グラフ（独立集合、クリーク、頂点被覆）

  • KaMIS：大きく疎なグラフの最大独立集合と頂点被覆。MIT。
  • Cliquer（Patric Östergård ほか）：最大クリークと最大重みクリークを厳密に探索します。GNU GPL。
  • PMC（Ryan A. Rossi）：並列の最大クリーク探索。GNU GPL v3 以降。
  • NetworkX（ソースコード）： 小さな実験向けの Python のグラフライブラリ。BSD 3-clause。

完全被覆

  • Donald E. Knuth の DLX1。 Algorithm 7.2.2.1X（dancing links による完全被覆）で、CWEB で書かれています。プログラムにも、それを載せたページにも、ライセンスの記載はありません。

巡回セールスマン問題とハミルトン閉路

  • Concorde （Applegate, Bixby, Chvátal, Cook）：対称な TSP を厳密に解くソルバー。 学術研究での利用は認められています。それ以外の利用には William Cook のライセンスが必要です。
  • LKH と LKH-3（Keld Helsgaun）：短い巡回路を見つける Lin–Kernighan–Helsgaun 法です。最短とは限りません。LKH はハミルトン閉路の問題も直接解けます。学術目的と非営利目的での利用に限ります。作者がすべての権利を保有しています。

汎用の制約ソルバーと整数計画ソルバー

  • RoundingSat（Jan Elffers, Jakob Nordström ほか）：OPBファイルを読む擬似ブールソルバー。MIT。次の論文で説明されています：Jan Elffers and Jakob Nordström, "Divide and conquer: towards faster pseudo-Boolean solving", Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18), 2018, pp. 1291–1299, doi:10.24963/ijcai.2018/180。
  • OR-Tools CP-SAT （Google。ソースコード）。Apache 2.0。
  • SCIP（ソースコード）： 制約整数計画。OPBファイルを読めます。Apache 2.0。
  • HiGHS（ソースコード）： 線形計画と混合整数計画。MIT。

さらに読む

  • Lance Fortnow, "The status of the P versus NP problem", Communications of the ACM 52(9), 2009, pp. 78–86. doi:10.1145/1562164.1562186
  • Scott Aaronson, "NP-complete problems and physical reality", ACM SIGACT News 36(1), 2005, pp. 30–52. doi:10.1145/1052796.1052804, arXiv:quant-ph/0502072 物理系（量子コンピューター、アナログ装置など）が NP 完全問題を効率よく解けるかどうか。
  • Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible, Princeton University Press, 2013. ISBN 978-0-691-15649-1。一般の読者向けです。
  • William J. Cook, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University Press, 2012. ISBN 978-0-691-15270-7.
  • Cristopher Moore and Stephan Mertens, The Nature of Computation, Oxford University Press, 2011. doi:10.1093/acprof:oso/9780199233212.001.0001 幅広く、読みやすい本です。書籍のサイトも見てください。
  • Avi Wigderson, Mathematics and Computation, Princeton University Press, 2019. doi:10.2307/j.ctvckq7xb 作者は、個人の学習用に最終稿を公開しています。