En informática , más específicamente en la teoría de la complejidad computacional , Computers and Intractability: A Guide to the Theory of NP-Completeness es un influyente libro de texto de Michael Garey y David S. Johnson . [1] Fue el primer libro exclusivamente sobre la teoría de NP-completitud e intratabilidad computacional . [2] El libro presenta un apéndice que proporciona un compendio completo de problemas NP-completos (que se actualizó en impresiones posteriores del libro). El libro ahora está desactualizado en algunos aspectos, ya que no cubre desarrollos más recientes, como el teorema de PCP.. Sin embargo, todavía está impreso y se considera un clásico: en un estudio de 2006, el motor de búsqueda CiteSeer enumeró el libro como la referencia más citada en la literatura informática. [3]
Autor | Michael R. Garey y David S. Johnson |
---|---|
País | Estados Unidos |
Idioma | inglés |
Serie | Una serie de libros sobre ciencias matemáticas |
Sujeto | Ciencias de la Computación |
Género | Libro de texto |
Editor | W. H. Freeman y compañía |
Fecha de publicación | 1979 |
Tipo de medio | Impresión |
Paginas | x + 338 |
ISBN | 0-7167-1045-5 |
OCLC | 247570676 |
Decimal Dewey | 519,4 |
Clase LC | QA76.6 .G35 |
Problemas abiertos
Otro apéndice del libro presentaba problemas para los que no se sabía si eran NP-completos o en P (o ninguno). Los problemas (con sus nombres originales) son:
- Isomorfismo gráfico
- Se sabe que este problema está en NP, pero se desconoce si es NP-completo.
- Homeomorfismo de subgrafo (para un gráfico fijo H )
- Género gráfico
- Finalización del gráfico de cuerdas
- Índice cromático [4]
- Problema de paridad del árbol de expansión [5]
- Dimensión de orden parcial
- Programación de 3 procesadores restringida por precedencia
- Este problema seguía abierto en 2016. [6]
- Programación lineal
- Unimodularidad total [7]
- Número compuesto
- Se sabe que las pruebas de composición están en P, pero la complejidad del problema de factorización de enteros estrechamente relacionado permanece abierta.
- Triangulación de longitud mínima [8]
- Se sabe que el problema 12 es NP-difícil, pero se desconoce si está en NP.
Recepción
Poco después de su publicación, el libro recibió críticas positivas de investigadores de renombre en el área de la informática teórica.
En su reseña, Ronald V. Book recomienda el libro a "cualquiera que desee aprender sobre el tema de NP-completitud", y menciona explícitamente el apéndice "extremadamente útil" con más de 300 problemas computacionales NP-difíciles. Concluye: "La informática necesita más libros como este". [9]
Harry R. Lewis elogia la prosa matemática de los autores: "El libro de Garey y Johnson es una exposición completa, clara y práctica de NP-completo. En muchos aspectos es difícil imaginar un mejor tratamiento del tema". Además, considera que el apéndice es "único" y "un punto de partida en los intentos de mostrar que los nuevos problemas son NP-completos". [10]
Veintitrés años después de la publicación del libro, Lance Fortnow , editor en jefe de la revista científica Transactions on Computational Theory , afirma: "Considero a Garey y Johnson como el libro más importante en la estantería de mi oficina. Todo científico informático debería tener este libro en sus estantes también. [...] Garey y Johnson tienen la mejor introducción a la complejidad computacional que he visto ". [11]
Ver también
Referencias
- ^ Garey, M. R .; Johnson, D. S. (1979). Victor Klee (ed.). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . Una serie de libros sobre ciencias matemáticas. San Francisco, California: W. H. Freeman and Co. págs. X + 338 . ISBN 0-7167-1045-5. Señor 0519066 .
- ^ Juris Hartmanis (1982). "Computadoras e intratabilidad: una guía para la teoría de NP-Completeness, reseña del libro". Revisión SIAM . 24 (1): 90–91. doi : 10.1137 / 1024022 . JSTOR 2029450 .
- ^ "Artículos más citados en Ciencias de la Computación - Septiembre de 2006 (CiteSeer.Continuity)" . Consultado el 3 de noviembre de 2007 .
- ^ NP-completo: Holyer, Ian (noviembre de 1981). "La NP-completitud de la coloración de bordes". Revista SIAM de Computación . 10 (4): 718–720. doi : 10.1137 / 0210055 .
- ^ En P: Lovász, L. Lovász, L .; Sós, VT (eds.). Métodos algebraicos en teoría de grafos, Volumen II (Coloquio Szeged, 1978) . Coloquia Mathematica Societatis János Bolyai, 25. Holanda Septentrional. págs. 495–517.
- ^ van Bevern, René; Bredereck, Robert; Bulteau, Laurent; Komusiewicz, cristiano; Talmon, Nimrod; Woeginger, Gerhard J. (2016). "Problemas de programación restringidos por precedencia parametrizados por ancho de orden parcial". DOOR 2016: Optimización discreta e investigación de operaciones . Apuntes de conferencias en informática . 9869 . Springer-Verlag . págs. 105-120. arXiv : 1605.00901 . doi : 10.1007 / 978-3-319-44914-2_9 .
- ^ En P: Seymour, PD (junio de 1980). "Descomposición de matroides regulares" (PDF) . Revista de Teoría Combinatoria, Serie B . 28 (3): 305–359. doi : 10.1016 / 0095-8956 (80) 90075-1 .
- ^ Es NP-hard: Mulzer, Wolfgang; Rote, Günter (2008), "La triangulación de peso mínimo es NP-hard", Revista de la ACM , 55 (2), Art. 11, arXiv : cs.CG/0601002 , doi : 10.1145 / 1346330.1346336 , MR 2417038
- ^ Libro de Ronald V. Revisión: Computadoras e intratabilidad: una guía para la teoría de NP-completitud Bull. Amer. Matemáticas. Soc. (NS), 3 (2), págs. 898–904, 1980
- ^ Harry R. Lewis, Revisión: Computadoras e intratabilidad: una guía para la teoría de NP-completitud , Journal of Symbolic Logic , vol. 48 (2), págs. 498–500, 1983
- ^ Lance Fortnow , Great Books: Computers and Intractability: A Guide to the Theory of NP-Completeness por Michael R. Garey y David S. Johnson. Blog de complejidad computacional, 30 de agosto de 2002.