stringtranslate.com

Las computadoras y la intratabilidad

Computers and Intractability: A Guide to the Theory of NP-Completeness es un libro de texto de Michael Garey y David S. Johnson . [1] Fue el primer libro exclusivamente sobre la teoría de la NP-completitud y la intratabilidad computacional . [2] El libro incluye un apéndice que proporciona un compendio completo de problemas NP-completos (que se actualizó en ediciones posteriores del libro). El libro ahora está desactualizado en algunos aspectos, ya que no cubre desarrollos más recientes como el teorema PCP . Sin embargo, todavía se imprime y se considera un clásico: en un estudio de 2006, el motor de búsqueda CiteSeer incluyó el libro como la referencia más citada en la literatura de ciencias de la computación. [3]

Problemas abiertos

En otro apéndice del libro se presentan problemas de los que no se sabe si son NP-completos o en P (o ninguno de los dos). Los problemas (con sus nombres originales) son:

  1. Isomorfismo de grafos
    Se sabe que este problema está en NP, pero se desconoce si es NP-completo.
  2. Homeomorfismo de subgrafos (para un grafo fijo H )
  3. Género gráfico
  4. Completamiento de grafos cordales
  5. Índice cromático [4]
  6. Problema de paridad del árbol de expansión [5]
  7. Dimensión de orden parcial
  8. Programación de 3 procesadores con precedencia restringida
    Este problema seguía abierto en 2016. [6]
  9. Programación lineal
  10. Unimodularidad total [7]
  11. Número compuesto
    Se sabe que la prueba de composición se realiza en P, pero la complejidad del problema de factorización de números enteros, estrechamente relacionado con él , permanece abierta.
  12. 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 aparición, el libro recibió críticas positivas por parte de reputados investigadores 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 la completitud NP", y menciona explícitamente el apéndice "extremadamente útil" con más de 300 problemas computacionales NP-hard. 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 minuciosa, clara y práctica de la NP-completitud. En muchos aspectos es difícil imaginar un tratamiento mejor del tema". Además, considera el apéndice como "único" y "un punto de partida en los intentos de demostrar que los nuevos problemas son NP-completos". [10]

Veintitrés años después de la publicación del libro, Lance Fortnow , editor jefe de la revista científica Transactions on Computational Theory , afirma: "Considero que Garey y Johnson es el libro más importante que tengo en la estantería de mi oficina. Todo científico informático también debería tener este libro en su estantería. [...] Garey y Johnson es la mejor introducción a la complejidad computacional que he visto jamás". [11]

Véase también

Referencias

  1. ^ Garey, M. R. ; Johnson, D. S. (1979). Victor Klee (ed.). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . Una serie de libros sobre ciencias matemáticas. San Francisco, California: W. H. Freeman and Co. ISBN 0-7167-1045-5.Sr. 0519066  .338 páginas. Copia en archive.org
  2. ^ Juris Hartmanis (1982). "Computadoras e intratabilidad: una guía para la teoría de la NP-completitud, reseña de libro". SIAM Review . 24 (1): 90–91. doi :10.1137/1024022. JSTOR  2029450.
  3. ^ "Artículos más citados en Ciencias de la Computación - Septiembre de 2006 (CiteSeer.Continuity)" . Consultado el 3 de noviembre de 2007 .
  4. ^ NP-completo: Holyer, Ian (noviembre de 1981). "La NP-completitud de la coloración de aristas". Revista SIAM de Computación . 10 (4): 718–720. doi :10.1137/0210055.
  5. ^ 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) . Colloquia Mathematica Societatis János Bolyai, 25. Holanda Septentrional. págs. 495–517.
  6. ^ van Bevern, René; Bredereck, Robert; Bulteau, Laurent; Komusiewicz, Christian; Talmon, Nimrod; Woeginger, Gerhard J. (2016). "Problemas de programación con restricciones de precedencia parametrizados por ancho de orden parcial". DOOR 2016: Optimización discreta e investigación de operaciones . Apuntes de clase en informática . Vol. 9869. Springer-Verlag . págs. 105–120. arXiv : 1605.00901 . doi :10.1007/978-3-319-44914-2_9.
  7. ^ En P: Seymour, PD (junio de 1980). "Descomposición de matroides regulares" (PDF) . Journal of Combinatorial Theory, Serie B. 28 ( 3): 305–359. doi : 10.1016/0095-8956(80)90075-1 .
  8. ^ ¿ Es NP-hard?: Mulzer, Wolfgang; Rote, Günter (2008), "La triangulación de peso mínimo es NP-hard", Journal of the ACM , 55 (2), Art. 11, arXiv : cs.CG/0601002 , doi :10.1145/1346330.1346336, MR  2417038
  9. ^ Ronald V. Book. Reseña: Computadoras e intratabilidad: una guía para la teoría de la completitud NP Bull. Amer. Math. Soc. (NS), 3 (2), págs. 898–904, 1980
  10. ^ Harry R. Lewis, Reseña: Computadoras e intratabilidad: una guía para la teoría de la completitud NP, Journal of Symbolic Logic , vol. 48 (2), págs. 498-500, 1983
  11. ^ Lance Fortnow , Grandes libros: Computadoras e intratabilidad: una guía para la teoría de la NP-completitud, de Michael R. Garey y David S. Johnson. Blog sobre complejidad computacional, 30 de agosto de 2002.