Beta-Version. Problem Forge ist neu und nur mit Einladung offen. Die Beta-Testphase läuft bis einschließlich 2026-11-30; die volle Öffnung ist am 2026-12-01 00:00 UTC. Es kann etwas kaputtgehen, und dann korrigieren wir vielleicht die Ranglisten. Die Schwierigkeit mancher Sprossen kann falsch sein. Während der Beta gibt es keine Preise, und die Prämie ist nicht offen. Dein Konto und dein Fortschritt bleiben, wenn die Beta endet. Bitte sag uns, was gut läuft und was schiefgeht: admin@problemforge.com.

Literatur

Mehr Lesestoff zu den 10 Problemen und Werkzeuge, die dir beim Klettern helfen. Fang mit Wikipedia an. Die Artikel und Bücher unten sind die klassischen Quellen.

Hintergrund: P, NP und NP-Vollständigkeit

  • Wikipedia: P versus NP problem, NP-completeness, Cook–Levin theorem.
  • Clay Mathematics Institute, P vs NP, eines der sieben Millennium-Probleme.
  • Stephen A. Cook, "The complexity of theorem-proving procedures", Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC '71), 1971, S. 151–158. doi:10.1145/800157.805047
  • Richard M. Karp, "Reducibility among combinatorial problems", in R. E. Miller und J. W. Thatcher (Hrsg.), Complexity of Computer Computations, Plenum Press, 1972, S. 85–103. doi:10.1007/978-1-4684-2001-2_9
  • Michael R. Garey und David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. ISBN 0-7167-1045-5. Der Standardkatalog NP-vollständiger Probleme.
  • Michael Sipser, Introduction to the Theory of Computation, 3. Aufl., Cengage Learning, 2013. ISBN 978-1-133-18779-0. Kapitel 7 führt in P, NP und NP-Vollständigkeit ein.
  • Sanjeev Arora und Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. doi:10.1017/CBO9780511804090

Boolesches Erfüllbarkeitsproblem (SAT)

  • Wikipedia: Boolean satisfiability problem, SAT solver.
  • Klassiker: Cook 1971 (oben), der erste Beweis für NP-Vollständigkeit. Zum Lösen: Martin Davis und Hilary Putnam, "A computing procedure for quantification theory", Journal of the ACM 7(3), 1960, S. 201–215, doi:10.1145/321033.321034; und Martin Davis, George Logemann und Donald Loveland, "A machine program for theorem-proving", Communications of the ACM 5(7), 1962, S. 394–397, doi:10.1145/368273.368557 (DPLL, die Methode hinter jedem modernen Solver).
  • Überblick: Armin Biere, Marijn Heule, Hans van Maaren und Toby Walsh (Hrsg.), Handbook of Satisfiability, 2. Aufl., IOS Press, 2021. doi:10.3233/FAIA336

3-SAT

  • Wikipedia: 3-satisfiability (ein Abschnitt des SAT-Artikels).
  • Klassiker: Uwe Schöning, "A probabilistic algorithm for k-SAT and constraint satisfaction problems", 40th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 1999, S. 410–414, doi:10.1109/SFFCS.1999.814612; Zeitschriftenfassung in Algorithmica 32(4), 2002, S. 615–623, doi:10.1007/s00453-001-0094-7. Eine einfache Methode, die zufällige Schritte macht. Bei 3-SAT ist sie schneller, als jeden Fall auszuprobieren.
  • Lehrbuch: Donald E. Knuth, The Art of Computer Programming, Volume 4B: Combinatorial Algorithms, Part 2, Addison-Wesley, 2023, Abschnitt 7.2.2.2 (Satisfiability). ISBN 0-201-03806-4.

Unabhängige Menge

Clique

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

Knotenüberdeckung

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

3-Färbung

  • Wikipedia: Graph coloring.
  • Klassiker: Daniel Brélaz, "New methods to color the vertices of a graph", Communications of the ACM 22(4), 1979, S. 251–256 (die Methode DSatur). doi:10.1145/359094.359101 Außerdem: Richard Beigel und David Eppstein, "3-coloring in time O(1.3289^n)", Journal of Algorithms 54(2), 2005, S. 168–204. doi:10.1016/j.jalgor.2004.06.008
  • Lehrbuch: R. M. R. Lewis, Guide to Graph Colouring: Algorithms and Applications, 2. Aufl., Springer, 2021. doi:10.1007/978-3-030-81054-2

Hamiltonkreis

  • Wikipedia: Hamiltonian path problem, Hamiltonian path.
  • Klassiker: Michael Held und Richard M. Karp, "A dynamic programming approach to sequencing problems", Journal of the Society for Industrial and Applied Mathematics 10(1), 1962, S. 196–210, doi:10.1137/0110015; und Richard Bellman, "Dynamic programming treatment of the travelling salesman problem", Journal of the ACM 9(1), 1962, S. 61–63, doi:10.1145/321105.321111. Modern: Andreas Björklund, "Determinant sums for undirected Hamiltonicity", SIAM Journal on Computing 43(1), 2014, S. 280–299. doi:10.1137/110839229
  • Überblick: Ronald J. Gould, "Advances on the Hamiltonian problem – a survey", Graphs and Combinatorics 19(1), 2003, S. 7–52. doi:10.1007/s00373-002-0492-x
  • Schwere Instanzen: Joeri Sleegers und 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. Frei zugänglich. doi:10.1007/s42979-022-01256-0

Problem des Handlungsreisenden (TSP)

  • Wikipedia: Travelling salesman problem.
  • Klassiker: G. Dantzig, R. Fulkerson und S. Johnson, "Solution of a large-scale traveling-salesman problem", Journal of the Operations Research Society of America 2(4), 1954, S. 393–410, doi:10.1287/opre.2.4.393; und S. Lin und B. W. Kernighan, "An effective heuristic algorithm for the traveling-salesman problem", Operations Research 21(2), 1973, S. 498–516, doi:10.1287/opre.21.2.498. Held und Karp 1962 (oben) ist das klassische exakte Verfahren mit dynamischer Programmierung.
  • Buch: David L. Applegate, Robert E. Bixby, Vašek Chvátal und William J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2006. ISBN 978-0-691-12993-8.

Ganzzahlige 0-1-Optimierung

Exakte Überdeckung durch 3-Mengen (X3C)

  • Wikipedia: Exact cover (exakte Überdeckung durch 3-Mengen ist der Fall, in dem jede Menge drei Elemente hat), Knuth's Algorithm X, Dancing links.
  • Klassiker: Donald E. Knuth, "Dancing links", in Millennial Perspectives in Computer Science, 2000, S. 187–214. arXiv:cs/0011047 Das Problem steht als [SP2] in Garey und Johnson 1979 (oben).
  • Lehrbuch: Donald E. Knuth, The Art of Computer Programming, Volume 4B, Addison-Wesley, 2023, Abschnitt 7.2.2.1 (Dancing links). ISBN 0-201-03806-4.

Solver und Werkzeuge

Jede Lizenz steht so da, wie das Projekt sie angibt. „Akademische Nutzung“ heißt, dass andere Nutzungen eine Erlaubnis brauchen können.

SAT

Graphen (unabhängige Menge, Clique, Knotenüberdeckung)

  • KaMIS: größte unabhängige Mengen und Knotenüberdeckungen großer, dünn besetzter Graphen. MIT.
  • Cliquer (Patric Östergård und andere): exakte Suche nach größten Cliquen und Cliquen mit größtem Gewicht. GNU GPL.
  • PMC (Ryan A. Rossi): parallele Suche nach größten Cliquen. GNU GPL v3 oder später.
  • NetworkX (Quellcode): Python-Bibliothek für Graphen, für kleine Experimente. BSD 3-clause.

Exakte Überdeckung

  • Donald E. Knuths DLX1, Algorithmus 7.2.2.1X (exakte Überdeckung mit Dancing Links), in CWEB. Weder das Programm noch die Seite, die es aufführt, nennt eine Lizenz.

Problem des Handlungsreisenden und Hamiltonkreis

  • Concorde (Applegate, Bixby, Chvátal, Cook): exakter Solver für das symmetrische TSP. Akademische Forschung ist erlaubt. Andere Nutzungen brauchen eine Lizenz von William Cook.
  • LKH und LKH-3 (Keld Helsgaun): die Lin-Kernighan-Helsgaun-Methode. Sie findet kurze Rundreisen, nicht immer die kürzeste. LKH löst auch direkt Hamiltonkreis-Probleme. Nur für akademische und nicht kommerzielle Nutzung. Der Autor behält sich alle Rechte vor.

Allgemeine Solver für Constraints und ganzzahlige Optimierung

  • RoundingSat (Jan Elffers, Jakob Nordström und andere): Pseudo-Boolean-Solver, der OPB-Dateien liest. MIT. Beschrieben in Jan Elffers und 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, S. 1291–1299, doi:10.24963/ijcai.2018/180.
  • OR-Tools CP-SAT (Google; Quellcode). Apache 2.0.
  • SCIP (Quellcode): Constraint Integer Programming; liest OPB-Dateien. Apache 2.0.
  • HiGHS (Quellcode): lineare und gemischt-ganzzahlige Optimierung. MIT.

Weiterführende Literatur

  • Lance Fortnow, "The status of the P versus NP problem", Communications of the ACM 52(9), 2009, S. 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 Ob physikalische Systeme (Quantencomputer, analoge Geräte und mehr) NP-vollständige Probleme effizient lösen könnten.
  • Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible, Princeton University Press, 2013. ISBN 978-0-691-15649-1. Für ein allgemeines Publikum.
  • 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 und Stephan Mertens, The Nature of Computation, Oxford University Press, 2011. doi:10.1093/acprof:oso/9780199233212.001.0001 Breit angelegt und gut lesbar. Siehe die Website zum Buch.
  • Avi Wigderson, Mathematics and Computation, Princeton University Press, 2019. doi:10.2307/j.ctvckq7xb Der Autor bietet eine letzte Entwurfsfassung zum persönlichen Studium an.