Saltar para o conteúdo

Computers and Intractability

Origem: Wikipédia, a enciclopédia livre.
Computadores e intratabilidade
Título original
(en) Computers and Intractability: A Guide to the Theory of NP-Completeness
Língua original
Autores
Michael Garey (en)
David Stifler Johnson
Genéro
Assunto
Editor

Computers and Intractability: A Guide to the Theory of NP-Completeness (Computadores e Intratabilidade: Um guia para a Teoria da NP-completude, tradução livre, não há edição em português) é um livro de Michael Garey e David S. Johnson de grande influência em ciência da computação, mais especificamente em teoria da complexidade computacional. Foi o primeiro livro a tratar exclusivamente de NP-completude e intratabilidade computacional. O livro apresenta um apêndice fornecendo um compêndio exaustivo dos problemas NP-completos (que foi atualizado em impressões posteriores do livro).O livro já está obsoleto em alguns aspectos, uma vez que não abrange o desenvolvimento mais recente na área como o teorema da Correspondência de Post. É, no entanto, ainda em versão impressa, considerado como um clássico: em um estudo de 2006, o motor de busca CiteSeer listou o livro como a referência mais citada na literatura de ciência da computação.

Outros problemas

[editar | editar código-fonte]

Outro apêndice do livro contou com problemas para os quais não se sabia se eram NP-completos ou em P (ou nenhum). Os problemas (com seus nomes originais) são:

  1. Isomorfismo de grafos
  2. Homomorfismo de subgrafos (para um dado grafo H)
  3. Gênero de grafos
  4. Compleção de grafo cordal
  5. Coloração de arestas[1]
  6. Problema da paridade de árvores de abrangência[2]
  7. Dimensão de ordem parcial
  8. Precedência restrita de escalonamento de 3 processadores
  9. Programação linear
  10. Amodularidade total[3]
  11. Teste de primalidade
    Teste de primalidade é conhecido por pertencer a P, mas a complexidade do problema  da fatoração inteira, intimamente relacionado, permanece aberta.
  12. Triangulação de comprimento mínimo[4]

A partir de 2015, um único problema ainda não foi classificado. Problema 12 é conhecido por ser NP-difícil, mas não se sabe se está em NP.

Assim que lançado, o livro recebeu críticas positivas por pesquisadores de renome na área de ciência da computação teórica.

Em sua avaliação, Ronald V. Book recomenda o livro para "qualquer um que deseje aprender sobre o tema da NP-completude", e menciona explicitamente o apêndice "extremamente útil" com mais de 300 problemas computacionais NP-difíceis. Ele conclui: "A ciência da computação precisa de mais livros como este."

Harry R. Lewis elogia o texto matemático dos autores: "O livro de Garey e Johnson é uma exposição completa, clara e prática da NP-completude. Em muitos aspectos, é difícil imaginar um melhor tratamento do assunto." Além disso, ele considera o apêndice como "único" e "como ponto de partida, na tentativa de mostrar novos problemas como sendo NP-completos".

Vinte e três anos após o livro aparecer, Lance Fortnow, editor-em-chefe das Operações de periódicos científicos na teoria computacional, declara: "Eu considero de Garey e Johnson o livro mais importante na estante do meu escritório. Todo cientista da computação deve ter este em suas prateleiras também. [...] Garey e Johnson tem a melhor introdução à complexidade computacional que eu já vi ".

Referências

  1. NP-complete: Holyer, Ian (novembro de 1981). «The NP-Completeness of Edge-Coloring». SIAM Journal on Computing. 10 (4): 718–20 
  2. In P: Lovász, L. Lovász, L.; Sós, V.T., eds. Algebraic Methods in Graph Theory, Volume II (Colloquium Szeged, 1978). Col: Colloquia Mathematica Societatis János Bolyai, 25. [S.l.]: North-Holland. pp. 495–517 
  3. In P: Seymour, P. D. (junho de 1980). «Decomposition of regular matroids». Journal of Combinatorial Theory, Series B. 28 (3): 305–59 
  4. Is NP-hard: Mulzer, Wolfgang; Rote, Günter (2008), «Minimum-weight triangulation is NP-hard», Journal of the ACM, 55 (2), Art. 11, MR 2417038, arXiv:cs.CG/0601002Acessível livremente, doi:10.1145/1346330.1346336