גרסת בטא. Problem Forge חדש ופתוח בהזמנה בלבד. תקופת בדיקת הבטא נמשכת עד 2026-11-30 (כולל); הפתיחה המלאה ב־2026-12-01 00:00 UTC. דברים עלולים להישבר, ואז ייתכן שנתקן את טבלאות המובילים. רמת הקושי של חלק מהשלבים עלולה להיות שגויה. אין פרסים בזמן הבטא, וגם הפרס לא פתוח. החשבון וההתקדמות שלכם יישארו כשהבטא תסתיים. אנא ספרו לנו מה עובד טוב ומה לא עובד: admin@problemforge.com.

מקורות

עוד קריאה על 10 הבעיות, וכלים שיעזרו לכם לטפס. התחילו בוויקיפדיה. המאמרים והספרים שלהלן הם המקורות הקלאסיים.

רקע: P, NP ו־NP-שלמות

  • ויקיפדיה: 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", בתוך R. E. Miller ו־J. W. Thatcher (עורכים), Complexity of Computer Computations, Plenum Press, 1972, pp. 85–103. doi:10.1007/978-1-4684-2001-2_9
  • Michael R. Garey ו־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, מהדורה 3, Cengage Learning, 2013. ISBN 978-1-133-18779-0. פרק 7 מציג את P, NP ו־NP-שלמות.
  • Sanjeev Arora ו־Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. doi:10.1017/CBO9780511804090

בעיית הספיקות הבוליאנית (SAT)

  • ויקיפדיה: Boolean satisfiability problem, SAT solver.
  • קלאסי: Cook 1971 (למעלה), ההוכחה הראשונה של NP-שלמות. לפתרון: Martin Davis ו־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 ו־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 ו־Toby Walsh (עורכים), Handbook of Satisfiability, מהדורה 2, IOS Press, 2021. doi:10.3233/FAIA336

3-SAT

  • ויקיפדיה: 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, סעיף 7.2.2.2 (Satisfiability). ISBN 0-201-03806-4.

קבוצה בלתי תלויה

קליקה

  • ויקיפדיה: Clique problem.
  • קלאסי: Coen Bron ו־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 ו־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

כיסוי צמתים

  • ויקיפדיה: Vertex cover.
  • קלאסי: G. L. Nemhauser ו־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 ו־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 ו־Saket Saurabh, Parameterized Algorithms, Springer, 2015. doi:10.1007/978-3-319-21275-3

צביעה בשלושה צבעים

  • ויקיפדיה: 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 ו־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, מהדורה 2, Springer, 2021. doi:10.1007/978-3-030-81054-2

מעגל המילטוני

  • ויקיפדיה: Hamiltonian path problem, Hamiltonian path.
  • קלאסי: Michael Held ו־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)

  • ויקיפדיה: Travelling salesman problem.
  • קלאסי: G. Dantzig, R. Fulkerson ו־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 ו־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 ו־Karp 1962 (למעלה) הוא התכנות הדינמי המדויק הקלאסי.
  • ספר: David L. Applegate, Robert E. Bixby, Vašek Chvátal ו־William J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2006. ISBN 978-0-691-12993-8.

תכנון בשלמים 0-1

כיסוי מדויק בשלשות (X3C)

  • ויקיפדיה: Exact cover (כיסוי מדויק בשלשות הוא המקרה שבו לכל קבוצה יש שלושה איברים), Knuth's Algorithm X, Dancing links.
  • קלאסי: Donald E. Knuth, "Dancing links", בתוך Millennial Perspectives in Computer Science, 2000, pp. 187–214. arXiv:cs/0011047 הבעיה מופיעה בתור [SP2] אצל Garey ו־Johnson 1979 (למעלה).
  • ספר לימוד: Donald E. Knuth, The Art of Computer Programming, Volume 4B, Addison-Wesley, 2023, סעיף 7.2.2.1 (Dancing links). ISBN 0-201-03806-4.

פותרים וכלים

כל רישיון מובא כפי שהפרויקט מציין אותו. "שימוש אקדמי" פירושו ששימושים אחרים עשויים לדרוש רשות.

SAT

גרפים (קבוצה בלתי תלויה, קליקה, כיסוי צמתים)

  • KaMIS: קבוצות בלתי תלויות מרביות וכיסויי צמתים של גרפים גדולים ודלילים. MIT.
  • Cliquer (Patric Östergård ואחרים): חיפוש מדויק של קליקה מרבית ושל קליקה במשקל מרבי. GNU GPL.
  • PMC (Ryan A. Rossi): קליקה מרבית במקביל. GNU GPL v3 ומעלה.
  • NetworkX (קוד מקור): ספריית גרפים ב־Python לניסויים קטנים. BSD 3-clause.

כיסוי מדויק

  • DLX1 של Donald E. Knuth, 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 ואחרים): פותר pseudo-Boolean שקורא קובצי OPB. MIT. מתואר אצל Jan Elffers ו־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 ו־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 המחבר מציע טיוטה סופית ללימוד אישי.