参考资料

关于这 10 个问题的更多阅读材料，以及帮助你攀登的工具。先从 Wikipedia 开始。下面的论文和书籍是经典来源。

背景：P、NP 与 NP 完全性

• Wikipedia：P versus NP problem、NP-completeness、Cook–Levin theorem。
• Clay Mathematics Institute，P vs NP，七个千禧年大奖难题之一。
• 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 条目中的一节）。
• 经典：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：Independent set (graph theory)。
• 经典：Robert Endre Tarjan and Anthony E. Trojanowski, "Finding a maximum independent set", SIAM Journal on Computing 6(3), 1977, pp. 537–546. doi:10.1137/0206038
• 教材：Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010. doi:10.1007/978-3-642-16533-7

团

• 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 整数规划

• Wikipedia：Integer programming、Pseudo-Boolean function。
• 经典：Karp 1972（见上）把 0-1 整数规划列为他的 21 个 NP 完全问题之一。关于求解：Ralph E. Gomory, "Outline of an algorithm for integer solutions to linear programs", Bulletin of the American Mathematical Society 64(5), 1958, pp. 275–278, doi:10.1090/S0002-9904-1958-10224-4（割平面法）；以及 Egon Balas, "An additive algorithm for solving linear programs with zero-one variables", Operations Research 13(4), 1965, pp. 517–546, doi:10.1287/opre.13.4.517（针对 0-1 变量的分支定界法）。
• 教材：Laurence A. Wolsey, Integer Programming, 2nd ed., Wiley, 2020. doi:10.1002/9781119606475 另见：Michele Conforti, Gérard Cornuéjols and Giacomo Zambelli, Integer Programming, Springer, 2014. doi:10.1007/978-3-319-11008-0
• 文件格式：Olivier Roussel and Vasco Manquinho, Input/Output Format and Solver Requirements for the Competitions of Pseudo-Boolean Solvers（OPB 格式），2016。Pseudo-Boolean Competition 2024 有结果、求解器和基准测试集。

3-集合精确覆盖 (X3C)

• Wikipedia：Exact cover（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

• Kissat（Armin Biere 等；源代码）。MIT。
• CaDiCaL（Armin Biere 等；源代码）。MIT。
• MiniSat（源代码）。MIT。描述见 Niklas Eén and Niklas Sörensson, "An extensible SAT-solver", Theory and Applications of Satisfiability Testing (SAT 2003), LNCS 2919, Springer, 2004, pp. 502–518, doi:10.1007/978-3-540-24605-3_37。
• CryptoMiniSat（源代码）。构建和运行所需的一切都是 MIT。另有一些额外文件是 GPLv2。
• The International SAT Competition：每年的结果、求解器源代码和基准测试集。
• Handbook of Satisfiability（见 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 作者提供最终草稿，供个人学习使用。