Computadores e intratabilidade -Computers and Intractability
 | |
| Autor | Michael R. Garey e David S. Johnson |
|---|---|
| País | Estados Unidos |
| Língua | inglês |
| Series | Uma série de livros em ciências matemáticas |
| Sujeito | Ciência da Computação |
| Gênero | Livro didático |
| Editor | W. H. Freeman and Company |
Data de publicação |
1979 |
| Tipo de mídia | Imprimir |
| Páginas | x + 338 |
| ISBN | 0-7167-1045-5 |
| OCLC | 247570676 |
| 519,4 | |
| Classe LC | QA76.6 .G35 |
Em ciência da computação , mais especificamente a teoria da complexidade computacional , Computadores e Intratabilidade: Um Guia para a Teoria da NP-Completude é um livro de Michael Garey e David S. Johnson . Foi o primeiro livro exclusivamente sobre a teoria da NP-completude e intratabilidade computacional . O livro apresenta um apêndice que fornece um compêndio completo de problemas NP-completos (que foi atualizado em impressões posteriores do livro). O livro está desatualizado em alguns aspectos, pois não cobre desenvolvimentos mais recentes, como o teorema PCP . No entanto, ainda está na versão impressa e é considerado um clássico: em um estudo de 2006, a ferramenta de busca CiteSeer listou o livro como a referência mais citada na literatura de ciência da computação.
Problemas abertos
Outro apêndice do livro apresentava 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 gráfico
- Este problema é conhecido por estar em NP, mas não se sabe se é NP-completo.
- Homeomorfismo do subgrafo (para um grafo fixo H )
- Gênero gráfico
- Conclusão do gráfico de acordes
- Índice cromático
- Problema de paridade de Spanning Tree
- Dimensão parcial do pedido
- Programação de 3 processadores com restrição de precedência
- Este problema ainda estava aberto em 2016.
- Programação linear
- Unimodularidade total
-
Número composto
- O teste de composição é conhecido por ser em P, mas a complexidade do problema de fatoração de inteiros intimamente relacionado permanece em aberto.
-
Triangulação de comprimento mínimo
- O problema 12 é conhecido por ser NP-difícil, mas não se sabe se é NP.
Recepção
Logo após seu lançamento, o livro recebeu críticas positivas de renomados pesquisadores da área de ciência da computação teórica.
Em sua revisão, Ronald V. Book recomenda o livro para "qualquer um que deseja aprender sobre o assunto NP-completude", e ele 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 a prosa matemática 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 tratamento melhor do assunto." Além disso, ele considera o apêndice como "único" e "como um ponto de partida nas tentativas de mostrar que novos problemas são NP-completos".
Vinte e três anos depois que o livro apareceu, Lance Fortnow , editor-chefe da revista científica Transactions on Computational Theory , afirma: "Considero Garey e Johnson o livro mais importante na estante de livros do meu escritório. Todo cientista da computação deveria ter isso livro em suas prateleiras também. [...] Garey and Johnson tem a melhor introdução à complexidade computacional que eu já vi. "