stringtranslate.com

Computadoras e intratabilidad

Computadoras e intratabilidad: una guía para la teoría de la integridad NP es un libro de texto de Michael Garey y David S. Johnson . [1] Fue el primer libro exclusivamente sobre la teoría de la completitud NP 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 está impreso y se considera un clásico: en un estudio de 2006, el motor de búsqueda CiteSeer lo catalogó como la referencia más citada en la literatura informática. [3]

Problemas abiertos

Otro apéndice del libro presentaba problemas de los cuales no se sabía si eran NP-completos o en P (o ninguno de los dos). Los problemas (con sus nombres originales) son:

  1. Isomorfismo gráfico
    Se sabe que este problema está en NP, pero se desconoce si es NP completo.
  2. Homeomorfismo de subgrafos (para un gráfico fijo H )
  3. Género gráfico
  4. Finalización del gráfico cordal
  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 prioridad restringida
    Este problema todavía estaba abierto en 2016. [6]
  9. Programación lineal
  10. Unimodularidad total [7]
  11. 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.
  12. Triangulación de longitud mínima [8]
    Se sabe que el problema 12 es NP-difícil, pero se desconoce si es NP.

Recepción

Poco después de su aparición, el libro recibió críticas positivas por parte 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 la completitud de NP", y menciona explícitamente el apéndice "extremadamente útil" con más de 300 problemas computacionales difíciles de NP. Y 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 exhaustiva, clara y práctica de la completitud NP. En muchos aspectos es difícil imaginar un mejor tratamiento del tema". Además, considera el apéndice como "único" y "como 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 aparición del libro, Lance Fortnow , editor en jefe de la revista científica Transactions on Computational Theory , afirma: "Considero que Garey y Johnson son el libro más importante de 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 jamás haya visto". [11]

Ver también

Referencias

  1. ^ Garey, MR ; Johnson, DS (1979). Víctor Klee (ed.). Computadoras e intratabilidad: una guía para la teoría de la integridad NP . Una serie de libros sobre ciencias matemáticas. San Francisco, California: W. H. Freeman and Co. ISBN 0-7167-1045-5. SEÑOR  0519066.338 páginas. Copiar en archive.org
  2. ^ Juris Hartmanis (1982). "Las computadoras y la intratabilidad: una guía para la teoría de la integridad NP, reseña del libro". Revisión SIAM . 24 (1): 90–91. doi :10.1137/1024022. JSTOR  2029450.
  3. ^ "Artículos más citados en informática - septiembre de 2006 (CiteSeer.Continuity)" . Consultado el 3 de noviembre de 2007 .
  4. ^ NP-completo: Holyer, Ian (noviembre de 1981). "La integridad NP de la coloración de bordes". 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, cristiano; Talmón, Nimrod; Woeginger, Gerhard J. (2016). "Problemas de programación con prioridad limitada parametrizados por ancho de orden parcial". PUERTA 2016: Optimización discreta e investigación de operaciones . Apuntes de conferencias sobre 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) . Revista de teoría combinatoria, serie B. 28 (3): 305–359. doi : 10.1016/0095-8956(80)90075-1 .
  8. ^ ¿ Es NP-duro: Mulzer, Wolfgang; Rote, Günter (2008), "La triangulación de peso mínimo es NP-duro", Revista de la ACM , 55 (2), art. 11, arXiv : cs.CG/0601002 , doi : 10.1145/1346330.1346336, SEÑOR  2417038
  9. ^ Ronald V. Libro. Revisión: Computadoras e intratabilidad: una guía para la teoría de la completitud NP Bull. América. Matemáticas. 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 de 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 integridad NP por Michael R. Garey y David S. Johnson. Blog de complejidad computacional, 30 de agosto de 2002.