Bètaversie. Problem Forge is nieuw en alleen op uitnodiging open. De bètatestperiode loopt tot en met 2026-11-30; de volledige opening is op 2026-12-01 00:00 UTC. Er kunnen dingen kapotgaan, en dan kunnen we de ranglijsten corrigeren. De moeilijkheid van sommige treden kan verkeerd zijn. Tijdens de bèta zijn er geen prijzen, en de beloning is niet open. Je account en je voortgang blijven als de bèta eindigt. Laat ons alsjeblieft weten wat er goed gaat en wat er misgaat: admin@problemforge.com.

Bronnen

Meer leesstof over de 10 problemen, en hulpmiddelen om te klimmen. Begin met Wikipedia. De artikelen en boeken hieronder zijn de klassieke bronnen.

Achtergrond: P, NP en NP-volledigheid

  • Wikipedia: P versus NP problem, NP-completeness, Cook–Levin theorem.
  • Clay Mathematics Institute, P vs NP, een van de zeven Millennium Prize Problems.
  • 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. De standaardcatalogus van NP-volledige problemen.
  • Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2013. ISBN 978-1-133-18779-0. Hoofdstuk 7 is een inleiding tot P, NP en NP-volledigheid.
  • Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. doi:10.1017/CBO9780511804090

Booleaans vervulbaarheidsprobleem (SAT)

  • Wikipedia: Boolean satisfiability problem, SAT solver.
  • Klassiek: Cook 1971 (hierboven), het eerste bewijs van NP-volledigheid. Over oplossen: 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; en 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, de methode achter elke moderne solver).
  • Overzicht: 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 (een deel van het artikel over SAT).
  • Klassiek: 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; tijdschriftversie in Algorithmica 32(4), 2002, pp. 615–623, doi:10.1007/s00453-001-0094-7. Een eenvoudige methode die willekeurige stappen zet. Op 3-SAT is ze sneller dan elke mogelijkheid proberen.
  • Leerboek: Donald E. Knuth, The Art of Computer Programming, Volume 4B: Combinatorial Algorithms, Part 2, Addison-Wesley, 2023, paragraaf 7.2.2.2 (Satisfiability). ISBN 0-201-03806-4.

Onafhankelijke verzameling

Kliek

  • Wikipedia: Clique problem.
  • Klassiek: 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
  • Overzicht: 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

Knoopbedekking

  • Wikipedia: Vertex cover.
  • Klassiek: 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 Ook: 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
  • Leerboek: 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-kleuring

Hamiltoncykel

  • Wikipedia: Hamiltonian path problem, Hamiltonian path.
  • Klassiek: 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; en 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. Modern: Andreas Björklund, "Determinant sums for undirected Hamiltonicity", SIAM Journal on Computing 43(1), 2014, pp. 280–299. doi:10.1137/110839229
  • Overzicht: 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
  • Moeilijke instanties: 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. Vrij toegankelijk. doi:10.1007/s42979-022-01256-0

Handelsreizigersprobleem (TSP)

  • Wikipedia: Travelling salesman problem.
  • Klassiek: 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; en 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 (hierboven) is het klassieke exacte dynamische programma.
  • Boek: 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.

Geheeltallige 0-1-programmering

Exacte overdekking met 3-verzamelingen (X3C)

  • Wikipedia: Exact cover (exacte overdekking met 3-verzamelingen is het geval waarin elke verzameling drie elementen heeft), Knuth's Algorithm X, Dancing links.
  • Klassiek: Donald E. Knuth, "Dancing links", in Millennial Perspectives in Computer Science, 2000, pp. 187–214. arXiv:cs/0011047 Het probleem staat als [SP2] in Garey and Johnson 1979 (hierboven).
  • Leerboek: Donald E. Knuth, The Art of Computer Programming, Volume 4B, Addison-Wesley, 2023, paragraaf 7.2.2.1 (Dancing links). ISBN 0-201-03806-4.

Solvers en hulpmiddelen

Elke licentie staat hier zoals het project haar vermeldt. “Academisch gebruik” betekent dat ander gebruik misschien toestemming vraagt.

SAT

Grafen (onafhankelijke verzameling, kliek, knoopbedekking)

  • KaMIS: maximale onafhankelijke verzamelingen en knoopbedekkingen van grote, ijle grafen. MIT.
  • Cliquer (Patric Östergård en anderen): exact zoeken naar een maximale kliek en een kliek met maximaal gewicht. GNU GPL.
  • PMC (Ryan A. Rossi): maximale kliek, parallel. GNU GPL v3 of later.
  • NetworkX (broncode): Python-bibliotheek voor grafen, voor kleine experimenten. BSD 3-clause.

Exacte overdekking

  • DLX1 van Donald E. Knuth, Algorithm 7.2.2.1X (exacte overdekking met dancing links), in CWEB. Het programma en de pagina waarop het staat, vermelden geen van beide een licentie.

Handelsreizigersprobleem en hamiltoncykel

  • Concorde (Applegate, Bixby, Chvátal, Cook): exacte solver voor het symmetrische TSP. Gebruik voor academisch onderzoek is toegestaan. Voor ander gebruik is een licentie van William Cook nodig.
  • LKH en LKH-3 (Keld Helsgaun): de methode van Lin–Kernighan–Helsgaun om korte rondreizen te vinden, niet altijd de kortste. LKH lost ook problemen van de hamiltoncykel direct op. Alleen voor academisch en niet-commercieel gebruik. De maker behoudt alle rechten.

Algemene solvers voor beperkingen en geheeltallige programmering

  • RoundingSat (Jan Elffers, Jakob Nordström en anderen): pseudo-booleaanse solver die OPB-bestanden leest. MIT. Beschreven in 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; broncode). Apache 2.0.
  • SCIP (broncode): geheeltallige programmering met beperkingen; leest OPB-bestanden. Apache 2.0.
  • HiGHS (broncode): lineaire en gemengd geheeltallige programmering. MIT.

Verder lezen

  • 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 Of fysische systemen (kwantumcomputers, analoge apparaten en meer) NP-volledige problemen efficiënt zouden kunnen oplossen.
  • Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible, Princeton University Press, 2013. ISBN 978-0-691-15649-1. Voor een breed publiek.
  • 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 Breed en goed leesbaar. Zie de website van het boek.
  • Avi Wigderson, Mathematics and Computation, Princeton University Press, 2019. doi:10.2307/j.ctvckq7xb De auteur biedt een laatste concept aan voor persoonlijke studie.