Computers and Intractability

Computadores e intratabilidade

Título original	(en) Computers and Intractability: A Guide to the Theory of NP-Completeness
Língua original	inglês
Autores	Michael Garey (en) David Stifler Johnson
Genéro	livro didático
Assunto	ciência de computadores
Editor	W. H. Freeman and Company

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:

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.
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

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

Veja também

Lista de problemas NP-completos

[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/0601002, doi:10.1145/1346330.1346336

[1]

[2]

[3]

[4]