Kaynaklar

10 problem hakkında daha fazla okuma ve tırmanmanıza yardım edecek araçlar. Wikipedia ile başlayın. Aşağıdaki makaleler ve kitaplar klasik kaynaklardır.

Arka plan: P, NP ve NP-tamlık

• Wikipedia: P versus NP problem, NP-completeness, Cook–Levin theorem.
• Clay Mathematics Institute, P vs NP: yedi Milenyum Probleminden biri.
• 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-tam problemlerin standart kataloğu.
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2013. ISBN 978-1-133-18779-0. 7. bölüm P, NP ve NP-tamlık kavramlarını tanıtır.
• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. doi:10.1017/CBO9780511804090

Boole sağlanabilirlik problemi (SAT)

• Wikipedia: Boolean satisfiability problem, SAT solver.
• Klasik: Cook 1971 (yukarıda), ilk NP-tamlık ispatı. Çözmek için: 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; ve 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: her modern çözücünün temelindeki yöntem).
• Genel bakış: 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 (SAT makalesinin bir bölümü).
• Klasik: 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; dergi sürümü: Algorithmica 32(4), 2002, pp. 615–623, doi:10.1007/s00453-001-0094-7. Rastgele adımlar atan basit bir yöntem. 3-SAT üzerinde her durumu tek tek denemekten daha hızlıdır.
• Ders kitabı: Donald E. Knuth, The Art of Computer Programming, Volume 4B: Combinatorial Algorithms, Part 2, Addison-Wesley, 2023, bölüm 7.2.2.2 (Satisfiability). ISBN 0-201-03806-4.

Bağımsız küme

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

Klik

• Wikipedia: Clique problem.
• Klasik: 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
• Genel bakış: 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

Düğüm örtüsü

• Wikipedia: Vertex cover.
• Klasik: 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 Ayrıca: 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
• Ders kitabı: 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-renklendirme

• Wikipedia: Graph coloring.
• Klasik: Daniel Brélaz, "New methods to color the vertices of a graph", Communications of the ACM 22(4), 1979, pp. 251–256 (DSatur yöntemi). doi:10.1145/359094.359101 Ayrıca: 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
• Ders kitabı: R. M. R. Lewis, Guide to Graph Colouring: Algorithms and Applications, 2nd ed., Springer, 2021. doi:10.1007/978-3-030-81054-2

Hamilton döngüsü

• Wikipedia: Hamiltonian path problem, Hamiltonian path.
• Klasik: 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; ve 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. Güncel: Andreas Björklund, "Determinant sums for undirected Hamiltonicity", SIAM Journal on Computing 43(1), 2014, pp. 280–299. doi:10.1137/110839229
• Genel bakış: 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
• Zor örnekler: 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. Açık erişim. doi:10.1007/s42979-022-01256-0

Gezgin satıcı problemi (TSP)

• Wikipedia: Travelling salesman problem.
• Klasik: 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; ve 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 ve Karp 1962 (yukarıda), klasik kesin dinamik programlama yöntemidir.
• Kitap: 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 tam sayılı programlama

• Wikipedia: Integer programming, Pseudo-Boolean function.
• Klasik: Karp 1972 (yukarıda), 0-1 tam sayılı programlamayı 21 NP-tam problemi arasında sayar. Çözmek için: 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 (kesme düzlemleri); ve 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 (0-1 değişkenler üzerinde dal ve sınır).
• Ders kitabı: Laurence A. Wolsey, Integer Programming, 2nd ed., Wiley, 2020. doi:10.1002/9781119606475 Ayrıca: Michele Conforti, Gérard Cornuéjols and Giacomo Zambelli, Integer Programming, Springer, 2014. doi:10.1007/978-3-319-11008-0
• Dosya biçimi: Olivier Roussel and Vasco Manquinho, Input/Output Format and Solver Requirements for the Competitions of Pseudo-Boolean Solvers (OPB biçimi), 2016. Pseudo-Boolean Competition 2024 sayfasında sonuçlar, çözücüler ve test problemi setleri var.

3-kümelerle tam örtü (X3C)

• Wikipedia: Exact cover (3-kümelerle tam örtü, her kümenin üç öğesi olduğu durumdur), Knuth's Algorithm X, Dancing links.
• Klasik: Donald E. Knuth, "Dancing links", in Millennial Perspectives in Computer Science, 2000, pp. 187–214. arXiv:cs/0011047 Problem, Garey ve Johnson 1979 (yukarıda) içinde [SP2] olarak geçer.
• Ders kitabı: Donald E. Knuth, The Art of Computer Programming, Volume 4B, Addison-Wesley, 2023, bölüm 7.2.2.1 (Dancing links). ISBN 0-201-03806-4.

Çözücüler ve araçlar

Her lisans, projenin belirttiği gibidir. "Akademik kullanım" ifadesi, başka kullanımlar için izin gerekebileceği anlamına gelir.

SAT

• Kissat (Armin Biere ve diğerleri; kaynak kod). MIT.
• CaDiCaL (Armin Biere ve diğerleri; kaynak kod). MIT.
• MiniSat (kaynak kod). MIT. Şurada anlatılmıştır: Niklas Eén and 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 (kaynak kod). Derlemek ve çalıştırmak için gereken her şey MIT lisanslıdır. Bazı ek dosyalar GPLv2 lisanslıdır.
• The International SAT Competition: yıllık sonuçlar, çözücülerin kaynak kodları ve test problemi setleri.
• Handbook of Satisfiability (bkz. SAT).

Graflar (bağımsız küme, klik, düğüm örtüsü)

• KaMIS: büyük seyrek grafların en büyük bağımsız kümeleri ve düğüm örtüleri. MIT.
• Cliquer (Patric Östergård ve diğerleri): en büyük klik ve en büyük ağırlıklı klik için kesin arama. GNU GPL.
• PMC (Ryan A. Rossi): paralel en büyük klik. GNU GPL v3 veya üstü.
• NetworkX (kaynak kod): küçük deneyler için Python graf kütüphanesi. BSD 3-clause.

Tam örtü

• Donald E. Knuth'un DLX1 programı: Algorithm 7.2.2.1X (dans eden bağlarla tam örtü), CWEB ile yazılmış. Ne programda ne de onu listeleyen sayfada bir lisans belirtilmiştir.

Gezgin satıcı ve Hamilton döngüsü

• Concorde (Applegate, Bixby, Chvátal, Cook): simetrik TSP için kesin çözücü. Akademik araştırma amaçlı kullanıma izin verilir. Başka kullanımlar için William Cook'tan lisans almak gerekir.
• LKH ve LKH-3 (Keld Helsgaun): kısa turlar bulmak için Lin–Kernighan–Helsgaun yöntemi; bulduğu tur her zaman en kısası değildir. LKH, Hamilton döngüsü problemlerini de doğrudan çözer. Yalnızca akademik ve ticari olmayan kullanım içindir. Yazar tüm hakları saklı tutar.

Genel kısıt programlama ve tam sayılı programlama çözücüleri

• RoundingSat (Jan Elffers, Jakob Nordström ve diğerleri): OPB dosyalarını okuyan bir pseudo-Boolean çözücü. MIT. Şurada anlatılmıştır: 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; kaynak kod). Apache 2.0.
• SCIP (kaynak kod): kısıtlı tam sayılı programlama; OPB dosyalarını okur. Apache 2.0.
• HiGHS (kaynak kod): doğrusal ve karma tam sayılı programlama. MIT.

Ek okumalar

• 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 Fiziksel sistemlerin (kuantum bilgisayarlar, analog cihazlar ve daha fazlası) NP-tam problemleri verimli biçimde çözüp çözemeyeceği.
• Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible, Princeton University Press, 2013. ISBN 978-0-691-15649-1. Genel okur için.
• 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 Geniş kapsamlı ve okunaklı. Bkz. kitabın sitesi.
• Avi Wigderson, Mathematics and Computation, Princeton University Press, 2019. doi:10.2307/j.ctvckq7xb Yazar, kişisel çalışma için bir son taslak sunuyor.