إصدار تجريبي. Problem Forge موقع جديد، والدخول إليه بدعوة فقط. تستمر فترة الاختبار التجريبي حتى 2026-11-30 ضمنًا، والافتتاح الكامل في 2026-12-01 00:00 UTC. قد تتعطل بعض الأشياء، وقد نصحّح لوحات الصدارة عندئذ. قد تكون صعوبة بعض الدرجات خاطئة. لا جوائز خلال النسخة التجريبية، والمكافأة غير مفتوحة. يبقى حسابك وتقدّمك عند انتهاء النسخة التجريبية. يُرجى إخبارنا بما يسير على ما يرام وبما يحدث من أخطاء: admin@problemforge.com.

المراجع

مزيد من القراءة عن المسائل العشر، وأدوات تساعدك على التسلّق. ابدأ بويكيبيديا. والأبحاث والكتب أدناه هي المصادر الكلاسيكية.

خلفية: 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", 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)

  • ويكيبيديا: 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

  • ويكيبيديا: 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.

المجموعة المستقلة

الزمرة

  • ويكيبيديا: 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

غطاء الرؤوس

  • ويكيبيديا: 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

التلوين بثلاثة ألوان

  • ويكيبيديا: 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

الدورة الهاميلتونية

  • ويكيبيديا: 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)

  • ويكيبيديا: 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

الغطاء التام بمجموعات ثلاثية (X3C)

  • ويكيبيديا: Exact cover (الغطاء التام بمجموعات ثلاثية هو الحالة التي تكون فيها كل مجموعة من ثلاثة عناصر)، Knuth's Algorithm X، Dancing links.
  • كلاسيكي: Donald E. Knuth, "Dancing links", in Millennial Perspectives in Computer Science, 2000, pp. 187–214. arXiv:cs/0011047 وتظهر المسألة باسم [SP2] في Garey and Johnson 1979 (أعلاه).
  • كتاب دراسي: 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

المخططات (المجموعة المستقلة، الزمرة، غطاء الرؤوس)

  • KaMIS: أكبر المجموعات المستقلة وأغطية الرؤوس في المخططات الكبيرة المتناثرة. MIT.
  • Cliquer (Patric Östergård وآخرون): بحث دقيق عن أكبر زمرة وعن الزمرة ذات أكبر وزن. GNU GPL.
  • PMC (Ryan A. Rossi): بحث متوازٍ عن أكبر زمرة. GNU GPL v3 أو أحدث.
  • NetworkX (المصدر): مكتبة Python للمخططات، للتجارب الصغيرة. BSD 3-clause.

الغطاء التام

  • برنامج DLX1 لـ Donald E. Knuth، الخوارزمية 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 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 ويتيح المؤلف مسودة نهائية للدراسة الشخصية.