참고 문헌

10개 문제에 대한 읽을거리와 사다리를 오르는 데 도움이 되는 도구예요. Wikipedia부터 시작하세요. 아래의 논문과 책은 고전적인 자료예요.

배경: P, NP, NP-완전성

• Wikipedia: P versus NP problem, NP-completeness, Cook–Levin theorem.
• Clay Mathematics Institute, P vs NP: 7개 밀레니엄 상 문제 중 하나예요.
• 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-집합 정확 덮개는 모든 집합의 원소가 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 저자가 개인 학습용으로 최종 원고를 공개하고 있어요.