Computers and Intractability
| Título original |
(en) Computers and Intractability: A Guide to the Theory of NP-Completeness |
|---|---|
| Língua original | |
| Autores | |
| 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:
- Isomorfismo de grafos
- Homomorfismo de subgrafos (para um dado grafo H)
- Gênero de grafos
- Compleção de grafo cordal
- Coloração de arestas[1]
- Problema da paridade de árvores de abrangência[2]
- Dimensão de ordem parcial
- Precedência restrita de escalonamento de 3 processadores
- Programação linear
- Amodularidade total[3]
- Teste de primalidade
- Teste de primalidade é conhecido por pertencer a P, mas a complexidade do problema da fatoração inteira, intimamente relacionado, permanece aberta.
- Teste de primalidade é conhecido por pertencer a P, mas a complexidade do problema da fatoração inteira, intimamente relacionado, permanece aberta.
- 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.
Aceitação[editar | editar código-fonte]
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
- ↑ NP-complete: Holyer, Ian (novembro de 1981). «The NP-Completeness of Edge-Coloring». SIAM Journal on Computing. 10 (4): 718–20
- ↑ 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
- ↑ In P: Seymour, P. D. (junho de 1980). «Decomposition of regular matroids». Journal of Combinatorial Theory, Series B. 28 (3): 305–59
- ↑ 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/0601002
, doi:10.1145/1346330.1346336
