Versão beta. O Problem Forge é novo e está aberto só por convite. O período de teste beta vai até 2026-11-30, inclusive; a abertura completa é em 2026-12-01 00:00 UTC. Algumas coisas podem quebrar, e aí podemos corrigir as classificações. A dificuldade de alguns degraus pode estar errada. Não há prêmios durante o beta, e a recompensa não está aberta. Sua conta e seu progresso continuam quando o beta terminar. Por favor, conte para nós o que der certo e o que der errado: admin@problemforge.com.

Referências

Mais leituras sobre os 10 problemas e ferramentas para ajudar você a escalar. Comece pela Wikipedia. Os artigos e livros abaixo são as fontes clássicas.

Contexto: P, NP e NP-completude

  • Wikipedia: P versus NP problem, NP-completeness, Cook–Levin theorem.
  • Clay Mathematics Institute, P vs NP, um dos sete Problemas do Prêmio do Milênio.
  • 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. O catálogo padrão de problemas NP-completos.
  • Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2013. ISBN 978-1-133-18779-0. O capítulo 7 apresenta P, NP e NP-completude.
  • Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. doi:10.1017/CBO9780511804090

Satisfatibilidade booleana (SAT)

  • Wikipedia: Boolean satisfiability problem, SAT solver.
  • Clássico: Cook 1971 (acima), a primeira prova de NP-completude. Para resolver: 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; e 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, o método por trás de todo solver moderno).
  • Visão geral: 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 (uma seção do artigo sobre SAT).
  • Clássico: 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; versão em revista em Algorithmica 32(4), 2002, pp. 615–623, doi:10.1007/s00453-001-0094-7. Um método simples que faz movimentos aleatórios. No 3-SAT, ele é mais rápido do que testar todos os casos.
  • Livro-texto: Donald E. Knuth, The Art of Computer Programming, Volume 4B: Combinatorial Algorithms, Part 2, Addison-Wesley, 2023, seção 7.2.2.2 (Satisfiability). ISBN 0-201-03806-4.

Conjunto independente

Clique

  • Wikipedia: Clique problem.
  • Clássico: 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
  • Visão geral: 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

Cobertura de vértices

  • Wikipedia: Vertex cover.
  • Clássico: 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 Também: 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
  • Livro-texto: 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-coloração

  • Wikipedia: Graph coloring.
  • Clássico: Daniel Brélaz, "New methods to color the vertices of a graph", Communications of the ACM 22(4), 1979, pp. 251–256 (o método DSatur). doi:10.1145/359094.359101 Também: 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
  • Livro-texto: R. M. R. Lewis, Guide to Graph Colouring: Algorithms and Applications, 2nd ed., Springer, 2021. doi:10.1007/978-3-030-81054-2

Ciclo hamiltoniano

  • Wikipedia: Hamiltonian path problem, Hamiltonian path.
  • Clássico: 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; e 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. Moderno: Andreas Björklund, "Determinant sums for undirected Hamiltonicity", SIAM Journal on Computing 43(1), 2014, pp. 280–299. doi:10.1137/110839229
  • Visão geral: 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
  • Instâncias difíceis: 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. Acesso aberto. doi:10.1007/s42979-022-01256-0

Caixeiro-viajante (TSP)

  • Wikipedia: Travelling salesman problem.
  • Clássico: 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; e 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 (acima) é o programa dinâmico exato clássico.
  • Livro: 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.

Programação inteira 0-1

Cobertura exata por 3-conjuntos (X3C)

  • Wikipedia: Exact cover (a cobertura exata por 3-conjuntos é o caso em que todo conjunto tem três elementos), Knuth's Algorithm X, Dancing links.
  • Clássico: Donald E. Knuth, "Dancing links", in Millennial Perspectives in Computer Science, 2000, pp. 187–214. arXiv:cs/0011047 O problema aparece como [SP2] em Garey and Johnson 1979 (acima).
  • Livro-texto: Donald E. Knuth, The Art of Computer Programming, Volume 4B, Addison-Wesley, 2023, seção 7.2.2.1 (Dancing links). ISBN 0-201-03806-4.

Solvers e ferramentas

Cada licença é a que o projeto declara. "Uso acadêmico" quer dizer que outros usos podem precisar de permissão.

SAT

Grafos (conjunto independente, clique, cobertura de vértices)

  • KaMIS: conjuntos independentes máximos e coberturas de vértices de grafos grandes e esparsos. MIT.
  • Cliquer (Patric Östergård e outros): busca exata de cliques máximas e de cliques de peso máximo. GNU GPL.
  • PMC (Ryan A. Rossi): clique máxima em paralelo. GNU GPL v3 ou posterior.
  • NetworkX (código-fonte): biblioteca de grafos em Python para experimentos pequenos. BSD 3-clause.

Cobertura exata

  • O DLX1 de Donald E. Knuth, Algorithm 7.2.2.1X (cobertura exata com dancing links), em CWEB. Nem o programa nem a página que o lista declaram uma licença.

Caixeiro-viajante e ciclo hamiltoniano

  • Concorde (Applegate, Bixby, Chvátal, Cook): solver exato para o TSP simétrico. O uso em pesquisa acadêmica é permitido. Outros usos precisam de uma licença de William Cook.
  • LKH e LKH-3 (Keld Helsgaun): o método Lin–Kernighan–Helsgaun para encontrar rotas curtos, nem sempre o mais curto. O LKH também resolve problemas de ciclo hamiltoniano diretamente. Apenas para uso acadêmico e não comercial. O autor reserva todos os direitos.

Solvers gerais de restrições e de programação inteira

  • RoundingSat (Jan Elffers, Jakob Nordström e outros): solver pseudobooleano que lê arquivos OPB. MIT. Descrito em 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; código-fonte). Apache 2.0.
  • SCIP (código-fonte): programação inteira com restrições; lê arquivos OPB. Apache 2.0.
  • HiGHS (código-fonte): programação linear e inteira mista. MIT.

Leituras extras

  • 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 Se sistemas físicos (computadores quânticos, dispositivos analógicos e outros) poderiam resolver problemas NP-completos de forma eficiente.
  • Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible, Princeton University Press, 2013. ISBN 978-0-691-15649-1. Para o público em geral.
  • 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 Amplo e fácil de ler. Veja o site do livro.
  • Avi Wigderson, Mathematics and Computation, Princeton University Press, 2019. doi:10.2307/j.ctvckq7xb O autor oferece uma versão final do rascunho para estudo pessoal.