Computers and Intractability: A Guide to the Theory of NP-Completeness

De Wikipedia, la enciclopedia libre
Computers and Intractability: A Guide to the Theory of NP-Completeness
de Michael Garey y David S. Johnson
Género Libro de texto
Tema(s) Ciencias de la computación
Idioma Inglés
Título original Computers and Intractability: A Guide to the Theory of NP-Completeness Ver y modificar los datos en Wikidata
Editorial W.H. Freeman y Cía.
País Estados Unidos Ver y modificar los datos en Wikidata
Fecha de publicación 1979
Formato Impreso
[editar datos en Wikidata]

En ciencias de la computación, más específicamente en el área de complejidad computacional, Computers and Intractability: A Guide to the Theory of NP-Completeness es un influyente libro de texto escrito por Michael Garey y David S. Johnson.

Fue el primer libro en tratar formalmente la NP-completitud y la intratabilidad.[1]​ El libro contiene un apéndice que provee un exhaustivo compendio de problemas de NP-completitud, el cual ha sido actualizado en las reimpresiones del libro. Actualmente se encuentra desactualizado en algunos aspectos, como el desarrollo del reciente teorema PCP, tema que no cubre. No obstante, se sigue imprimiendo y es considerado un clásico: en un estudio de 2006, el motor de búsqueda CiteSeer listó este libro como el más citado en la literatura de ciencias de la computación.[2]​

Referencias[editar]

  1. ↑ Juris Hartmanis (1982). «Computers and Intractability: A Guide to the Theory of NP-Completeness, book review». SIAM Review (en inglés) 24 (1): 90-91. Consultado el 3 de julio de 2008. 
  2. ↑ «Most cited articles in Computer Science - September 2006 (CiteSeer.Continuity)». Consultado el 3 de noviembre de 2007. 
Obtenido de «https://es.wikipedia.org/w/index.php?title=Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness&oldid=118923363»