Computers and Intractability

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
Gênero
Assunto
Editor

editar - editar código-fonte - editar WikidataDocumentação da predefinição

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

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
  6. Problema da paridade de árvores de abrangência
  7. Dimensão de ordem parcial
  8. Precedência restrita de escalonamento de 3 processadores
  9. Programação linear
  10. Amodularidade total
  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

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.

Aceitação

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

Ver também