Références

D'autres lectures sur les 10 problèmes, et des outils pour vous aider à grimper. Commencez par Wikipédia. Les articles et les livres ci-dessous sont les sources classiques.

Contexte : P, NP et NP-complétude

• Wikipédia : P versus NP problem, NP-completeness, Cook–Levin theorem.
• Clay Mathematics Institute, P vs NP, l'un des sept problèmes du prix du millénaire.
• 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", dans R. E. Miller et J. W. Thatcher (dir.), Complexity of Computer Computations, Plenum Press, 1972, pp. 85–103. doi:10.1007/978-1-4684-2001-2_9
• Michael R. Garey et David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. ISBN 0-7167-1045-5. Le catalogue de référence des problèmes NP-complets.
• Michael Sipser, Introduction to the Theory of Computation, 3e éd., Cengage Learning, 2013. ISBN 978-1-133-18779-0. Le chapitre 7 présente P, NP et la NP-complétude.
• Sanjeev Arora et Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. doi:10.1017/CBO9780511804090

Satisfaisabilité booléenne (SAT)

• Wikipédia : Boolean satisfiability problem, SAT solver.
• Classique : Cook 1971 (ci-dessus), la première preuve de NP-complétude. Pour la résolution : Martin Davis et Hilary Putnam, "A computing procedure for quantification theory", Journal of the ACM 7(3), 1960, pp. 201–215, doi:10.1145/321033.321034 ; et Martin Davis, George Logemann et Donald Loveland, "A machine program for theorem-proving", Communications of the ACM 5(7), 1962, pp. 394–397, doi:10.1145/368273.368557 (DPLL, la méthode à la base de tous les solveurs modernes).
• Synthèse : Armin Biere, Marijn Heule, Hans van Maaren et Toby Walsh (dir.), Handbook of Satisfiability, 2e éd., IOS Press, 2021. doi:10.3233/FAIA336

3-SAT

• Wikipédia : 3-satisfiability (une section de l'article sur SAT).
• Classique : 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 ; version revue dans Algorithmica 32(4), 2002, pp. 615–623, doi:10.1007/s00453-001-0094-7. Une méthode simple qui fait des pas au hasard. Sur 3-SAT, elle est plus rapide que d'essayer tous les cas.
• Manuel : 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.

Ensemble indépendant

• Wikipédia : Independent set (graph theory).
• Classique : Robert Endre Tarjan et Anthony E. Trojanowski, "Finding a maximum independent set", SIAM Journal on Computing 6(3), 1977, pp. 537–546. doi:10.1137/0206038
• Manuel : Fedor V. Fomin et Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010. doi:10.1007/978-3-642-16533-7

Clique

• Wikipédia : Clique problem.
• Classique : Coen Bron et 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
• Synthèse : Qinghua Wu et 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

Couverture par sommets

• Wikipédia : Vertex cover.
• Classique : G. L. Nemhauser et L. E. Trotter, "Vertex packings: structural properties and algorithms", Mathematical Programming 8(1), 1975, pp. 232–248. doi:10.1007/BF01580444 Voir aussi : Jianer Chen, Iyad A. Kanj et 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
• Manuel : Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk et Saket Saurabh, Parameterized Algorithms, Springer, 2015. doi:10.1007/978-3-319-21275-3

3-coloration

• Wikipédia : Graph coloring.
• Classique : Daniel Brélaz, "New methods to color the vertices of a graph", Communications of the ACM 22(4), 1979, pp. 251–256 (la méthode DSatur). doi:10.1145/359094.359101 Voir aussi : Richard Beigel et 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
• Manuel : R. M. R. Lewis, Guide to Graph Colouring: Algorithms and Applications, 2e éd., Springer, 2021. doi:10.1007/978-3-030-81054-2

Cycle hamiltonien

• Wikipédia : Hamiltonian path problem, Hamiltonian path.
• Classique : Michael Held et 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 ; et 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. Récent : Andreas Björklund, "Determinant sums for undirected Hamiltonicity", SIAM Journal on Computing 43(1), 2014, pp. 280–299. doi:10.1137/110839229
• Synthèse : 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
• Instances difficiles : Joeri Sleegers et 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. En accès libre. doi:10.1007/s42979-022-01256-0

Voyageur de commerce (TSP)

• Wikipédia : Travelling salesman problem.
• Classique : G. Dantzig, R. Fulkerson et 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 ; et S. Lin et 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 et Karp 1962 (ci-dessus) est la méthode exacte classique par programmation dynamique.
• Livre : David L. Applegate, Robert E. Bixby, Vašek Chvátal et William J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2006. ISBN 978-0-691-12993-8.

Programmation en nombres entiers 0-1

• Wikipédia : Integer programming, Pseudo-Boolean function.
• Classique : Karp 1972 (ci-dessus) cite la programmation en nombres entiers 0-1 parmi ses 21 problèmes NP-complets. Pour la résolution : 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 (plans de coupe) ; et 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 (séparation et évaluation sur des variables 0-1).
• Manuel : Laurence A. Wolsey, Integer Programming, 2e éd., Wiley, 2020. doi:10.1002/9781119606475 Voir aussi : Michele Conforti, Gérard Cornuéjols et Giacomo Zambelli, Integer Programming, Springer, 2014. doi:10.1007/978-3-319-11008-0
• Le format de fichier : Olivier Roussel et Vasco Manquinho, Input/Output Format and Solver Requirements for the Competitions of Pseudo-Boolean Solvers (le format OPB), 2016. La Pseudo-Boolean Competition 2024 donne des résultats, des solveurs et des jeux de tests.

Couverture exacte par 3-ensembles (X3C)

• Wikipédia : Exact cover (la couverture exacte par 3-ensembles est le cas où chaque ensemble a trois éléments), Knuth's Algorithm X, Dancing links.
• Classique : Donald E. Knuth, "Dancing links", dans Millennial Perspectives in Computer Science, 2000, pp. 187–214. arXiv:cs/0011047 Le problème figure sous [SP2] dans Garey et Johnson 1979 (ci-dessus).
• Manuel : 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.

Solveurs et outils

Chaque licence est celle qu'indique le projet. « Usage académique » veut dire que les autres usages peuvent demander une autorisation.

SAT

• Kissat (Armin Biere et d'autres ; source). MIT.
• CaDiCaL (Armin Biere et d'autres ; source). MIT.
• MiniSat (source). MIT. Décrit dans Niklas Eén et 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 (source). MIT pour tout ce qu'il faut pour le compiler et le lancer. Quelques fichiers en plus sont sous GPLv2.
• The International SAT Competition : résultats annuels, sources des solveurs et jeux de tests.
• Handbook of Satisfiability (voir SAT).

Graphes (ensemble indépendant, clique, couverture par sommets)

• KaMIS : ensembles indépendants maximum et couvertures par sommets de grands graphes creux. MIT.
• Cliquer (Patric Östergård et d'autres) : recherche exacte de clique maximum et de clique de poids maximum. GNU GPL.
• PMC (Ryan A. Rossi) : clique maximum en parallèle. GNU GPL v3 ou ultérieure.
• NetworkX (source) : bibliothèque Python de graphes, pour de petites expériences. BSD 3-clause.

Couverture exacte

• DLX1 de Donald E. Knuth, algorithme 7.2.2.1X (couverture exacte par « dancing links »), en CWEB. Ni le programme ni la page qui le liste n'indiquent de licence.

Voyageur de commerce et cycle hamiltonien

• Concorde (Applegate, Bixby, Chvátal, Cook) : solveur exact du TSP symétrique. L'usage pour la recherche académique est autorisé. Les autres usages demandent une licence de William Cook.
• LKH et LKH-3 (Keld Helsgaun) : la méthode de Lin–Kernighan–Helsgaun, qui trouve des tournées courtes, pas toujours les plus courtes. LKH résout aussi directement les problèmes de cycle hamiltonien. Pour un usage académique et non commercial seulement. L'auteur se réserve tous les droits.

Solveurs généraux de contraintes et de programmation en nombres entiers

• RoundingSat (Jan Elffers, Jakob Nordström et d'autres) : solveur pseudo-booléen qui lit les fichiers OPB. MIT. Décrit dans Jan Elffers et 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 ; source). Apache 2.0.
• SCIP (source) : programmation en nombres entiers sous contraintes ; lit les fichiers OPB. Apache 2.0.
• HiGHS (source) : programmation linéaire et en nombres entiers mixte. MIT.

Pour aller plus loin

• 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 Des systèmes physiques (ordinateurs quantiques, dispositifs analogiques, etc.) pourraient-ils résoudre efficacement les problèmes NP-complets ?
• Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible, Princeton University Press, 2013. ISBN 978-0-691-15649-1. Pour le grand public.
• 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 et Stephan Mertens, The Nature of Computation, Oxford University Press, 2011. doi:10.1093/acprof:oso/9780199233212.001.0001 Large et agréable à lire. Voir le site du livre.
• Avi Wigderson, Mathematics and Computation, Princeton University Press, 2019. doi:10.2307/j.ctvckq7xb L'auteur propose une version finale du manuscrit pour l'étude personnelle.