En la teoría de la complejidad computacional , un problema es NP-completo cuando:
- un algoritmo de búsqueda de fuerza bruta puede resolverlo, y la exactitud de cada solución se puede verificar rápidamente, y
- el problema se puede utilizar para simular cualquier otro problema con una capacidad de solución similar.
El nombre "NP-completo" es la abreviatura de "tiempo polinomial no determinista completo". En este nombre, "no determinista" se refiere a máquinas de Turing no deterministas , una forma de formalizar matemáticamente la idea de un algoritmo de búsqueda de fuerza bruta. El tiempo polinomial se refiere a una cantidad de tiempo que se considera "rápida" para que un algoritmo determinista verifique una única solución, o para que una máquina de Turing no determinista realice toda la búsqueda. " Completo " se refiere a la propiedad de poder simular todo en la misma clase de complejidad .
Más precisamente, cada entrada al problema debe asociarse con un conjunto de soluciones de longitud polinomial, cuya validez se puede probar rápidamente (en tiempo polinomial ), [1] de manera que la salida para cualquier entrada sea "sí" si la solución establece no está vacío y "no" si está vacío. La clase de complejidad de problemas de esta forma se llama NP , una abreviatura de "tiempo polinomial no determinista". Se dice que un problema es NP-difícil si todo en NP se puede transformar en tiempo polinomial en él, aunque no esté en NP. Por el contrario, un problema es NP-completo si está tanto en NP como NP-hard. Los problemas NP-completos representan los problemas más difíciles en NP. Si cualquier problema NP-completo tiene un algoritmo de tiempo polinomial, todos los problemas en NP lo tienen. El conjunto de problemas NP-completos a menudo se denota mediante NP-C o NPC .
Aunque la solución a un problema NP-completo se puede verificar "rápidamente", no existe una forma conocida de encontrar una solución rápidamente. Es decir, el tiempo necesario para resolver el problema utilizando cualquier algoritmo conocido en la actualidad aumenta rápidamente a medida que crece el tamaño del problema. Como consecuencia, determinar si es posible resolver estos problemas rápidamente, llamado problema P versus NP , es uno de los problemas fundamentales sin resolver en la ciencia de la computación actual.
Si bien un método para calcular las soluciones a los problemas de NP-completo permanece rápidamente sin descubrir, los informáticos y programadores todavía se encuentran con frecuencia con problemas de NP-completo. Los problemas NP-completos a menudo se abordan mediante métodos heurísticos y algoritmos de aproximación .
Descripción general
Los problemas NP-completos están en NP , el conjunto de todos los problemas de decisión cuyas soluciones se pueden verificar en tiempo polinomial; NP puede definirse de manera equivalente como el conjunto de problemas de decisión que se pueden resolver en tiempo polinomial en una máquina de Turing no determinista . Un problema p en NP es NP-completo si todos los demás problemas en NP pueden transformarse (o reducirse) en p en tiempo polinomial.
No se sabe si todos los problemas de NP pueden resolverse rápidamente; esto se denomina problema P versus NP . Pero si cualquier problema NP-completo puede resolverse rápidamente, entonces todos los problemas en NP pueden, porque la definición de un problema NP-completo establece que cada problema en NP debe ser rápidamente reducible a cada problema NP-completo (es decir, puede reducirse en tiempo polinomial). Debido a esto, a menudo se dice que los problemas NP-completos son más difíciles o más difíciles que los problemas NP en general.
Definicion formal
Un problema de decisión es NP-completo si:
se puede demostrar que está en NP demostrando que una solución candidata para se puede verificar en tiempo polinomial.
Tenga en cuenta que un problema que satisface la condición 2 se dice que es NP-difícil , satisfaga o no la condición 1. [3]
Una consecuencia de esta definición es que si tuviéramos un algoritmo de tiempo polinomial (en un UTM , o cualquier otra máquina abstracta equivalente a Turing ) para, podríamos resolver todos los problemas en NP en tiempo polinomial.
Fondo
El concepto de NP-completo se introdujo en 1971 (véase el teorema de Cook-Levin ), aunque el término NP-completo se introdujo más tarde. En la conferencia STOC de 1971 , hubo un feroz debate entre los científicos informáticos sobre si los problemas NP-completos podrían resolverse en tiempo polinomial en una máquina de Turing determinista . John Hopcroft llevó a todos en la conferencia a un consenso de que la cuestión de si los problemas NP-completos se pueden resolver en tiempo polinomial debería posponerse para resolverse en una fecha posterior, ya que nadie tenía pruebas formales de sus afirmaciones de una forma u otra. . Esto se conoce como "la cuestión de si P = NP".
Nadie ha sido capaz todavía de determinar de manera concluyente si los problemas NP-completos son de hecho solucionables en tiempo polinomial, lo que convierte a este en uno de los grandes problemas matemáticos sin resolver . El Clay Mathematics Institute ofrece una recompensa de 1 millón de dólares a cualquiera que tenga una prueba formal de que P = NP o que P ≠ NP.
El teorema de Cook-Levin establece que el problema de satisfacibilidad booleano es NP-completo. En 1972, Richard Karp demostró que varios otros problemas también eran NP-completos (ver 21 problemas NP-completos de Karp ); por tanto, existe una clase de problemas NP-completos (además del problema de satisfacibilidad booleano). Desde los resultados originales, se ha demostrado que miles de otros problemas son NP-completos mediante reducciones de otros problemas que previamente demostraron ser NP-completos; muchos de estos problemas se recogen en el libro de 1979 de Garey y Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness . [4]
Problemas NP-completos
Un ejemplo interesante es el problema de isomorfismo de grafos , el problema de la teoría de grafos para determinar si existe un isomorfismo de grafos entre dos grafos. Dos gráficos son isomórficos si uno se puede transformar en el otro simplemente cambiando el nombre de los vértices . Considere estos dos problemas:
- Graficar isomorfismo: ¿Es la gráfica G 1 isomorfa a la gráfica G 2 ?
- Isomorfismo de subgrafo: ¿Es el gráfico G 1 isomorfo a un subgrafo del gráfico G 2 ?
El problema del isomorfismo del subgrafo es NP-completo. Se sospecha que el problema del isomorfismo de la gráfica no está ni en P ni en NP-completo, aunque sí en NP. Este es un ejemplo de un problema que se cree que es difícil , pero que no se considera NP-completo.
La forma más fácil de probar que un problema nuevo es NP-completo es primero demostrar que está en NP y luego reducirle algún problema conocido de NP-completo. Por lo tanto, es útil conocer una variedad de problemas NP-completos. La siguiente lista contiene algunos problemas conocidos que son NP-completos cuando se expresan como problemas de decisión.
- Problema de satisfacibilidad booleano (SAT)
- Problema de la mochila
- Problema del camino hamiltoniano
- Problema del vendedor ambulante (versión de decisión)
- Problema de isomorfismo de subgrafo
- Problema de suma de subconjuntos
- Problema de camarilla
- Problema de cobertura de vértice
- Problema de conjuntos independientes
- Problema de conjunto dominante
- Problema de coloración de gráficos
A la derecha hay un diagrama de algunos de los problemas y las reducciones que se usan típicamente para probar su NP-completo. En este diagrama, los problemas se reducen de abajo hacia arriba. Tenga en cuenta que este diagrama es engañoso como descripción de la relación matemática entre estos problemas, ya que existe una reducción de tiempo polinomial entre dos problemas NP-completos cualesquiera; pero indica dónde ha sido más fácil demostrar esta reducción de tiempo polinomial.
A menudo, existe una pequeña diferencia entre un problema en P y un problema NP-completo. Por ejemplo, el problema de satisfacibilidad 3 , una restricción del problema de satisfacibilidad booleano, sigue siendo NP-completo, mientras que el problema de satisfacibilidad 2 ligeramente más restringido está en P (específicamente, NL-completo ), y el máximo ligeramente más general. 2-sat. El problema es de nuevo NP-completo. Determinar si un gráfico se puede colorear con 2 colores está en P, pero con 3 colores es NP-completo, incluso cuando se restringe a gráficos planos . Determinar si un gráfico es un ciclo o es bipartito es muy fácil (en L ), pero encontrar un subgráfico máximo bipartito o ciclo máximo es NP-completo. Una solución del problema de la mochila dentro de cualquier porcentaje fijo de la solución óptima se puede calcular en tiempo polinomial, pero encontrar la solución óptima es NP-completo.
Resolver problemas NP-completos
En la actualidad, todos los algoritmos conocidos para problemas NP-completos requieren un tiempo superpolinomial en el tamaño de entrada, y se desconoce si existen algoritmos más rápidos.
Las siguientes técnicas se pueden aplicar para resolver problemas computacionales en general y, a menudo, dan lugar a algoritmos sustancialmente más rápidos:
- Aproximación : en lugar de buscar una solución óptima, busque una solución que sea como mucho un factor de uno óptimo.
- Aleatorización : use la aleatoriedad para obtener un tiempo de ejecución promedio más rápido y permita que el algoritmo falle con una pequeña probabilidad. Nota: El método de Monte Carlo no es un ejemplo de un algoritmo eficiente en este sentido específico, aunque pueden serlo enfoques evolutivos como los algoritmos genéticos .
- Restricción: Al restringir la estructura de la entrada (por ejemplo, a gráficos planos), generalmente son posibles algoritmos más rápidos.
- Parametrización : a menudo hay algoritmos rápidos si ciertos parámetros de la entrada son fijos.
- Heurístico : Un algoritmo que funciona "razonablemente bien" en muchos casos, pero para el cual no hay pruebas de que sea siempre rápido y siempre produzca un buen resultado. A menudo se utilizan enfoques metaheurísticos .
Un ejemplo de un algoritmo heurístico es un subóptimo algoritmo codicioso de coloración utilizado para colorear gráficos durante la fase de asignación de registros de algunos compiladores, una técnica llamada asignación global de registros para colorear gráficos . Cada vértice es una variable, los bordes se dibujan entre las variables que se están utilizando al mismo tiempo y los colores indican el registro asignado a cada variable. Debido a que la mayoría de las máquinas RISC tienen un número bastante grande de registros de propósito general, incluso un enfoque heurístico es efectivo para esta aplicación.
Integridad bajo diferentes tipos de reducción
En la definición de NP-completa dada anteriormente, el término reducción se usó en el significado técnico de una reducción de muchos uno en tiempo polinómico .
Otro tipo de reducción es la reducción de Turing en tiempo polinómico. Un problema ¿Es Turing en tiempo polinómico reducible a un problema? si, dada una subrutina que resuelve en tiempo polinomial, se podría escribir un programa que llame a esta subrutina y resuelva en tiempo polinomial. Esto contrasta con la reducibilidad muchos-uno, que tiene la restricción de que el programa solo puede llamar a la subrutina una vez, y el valor de retorno de la subrutina debe ser el valor de retorno del programa.
Si uno define el análogo a NP-completo con reducciones de Turing en lugar de reducciones de muchos-uno, el conjunto de problemas resultante no será menor que NP-completo; es una pregunta abierta si será más grande.
Otro tipo de reducción que también se utiliza a menudo para definir NP-completitud es la reducción de muchos uno en el espacio logarítmico, que es una reducción de muchos uno que se puede calcular con solo una cantidad de espacio logarítmica. Dado que todos los cálculos que se pueden realizar en el espacio logarítmico también se pueden realizar en el tiempo polinomial, se deduce que si hay una reducción de muchos uno en el espacio logarítmico, también hay una reducción de muchos uno en el tiempo polinomial. Este tipo de reducción es más refinado que las reducciones muchos-uno en tiempo polinómico más habituales y nos permite distinguir más clases como P-completo . Si bajo estos tipos de reducciones, la definición de cambios NP-completos sigue siendo un problema abierto. Todos los problemas NP-completo actualmente conocidos son NP-completo bajo reducciones de espacio logarítmico. Todos los problemas NP-completos actualmente conocidos siguen siendo NP-completos incluso con reducciones mucho más débiles. [5] Sin embargo, se sabe que las reducciones de AC 0 definen una clase estrictamente más pequeña que las reducciones de tiempo polinómico. [6]
Nombrar
Según Donald Knuth , el nombre "NP-completo" fue popularizado por Alfred Aho , John Hopcroft y Jeffrey Ullman en su célebre libro de texto "El diseño y análisis de algoritmos informáticos". Él informa que introdujeron el cambio en las galeradas del libro (de "polinomialmente completo"), de acuerdo con los resultados de una encuesta que había realizado a la comunidad de ciencias de la computación teórica . [7] Otras sugerencias hechas en la encuesta [8] incluyeron " Herculean ", "formidable", Steiglitz "hard-boiled" en honor a Cook, y el acrónimo de Shen Lin "PET", que significa "tiempo probablemente exponencial". , pero dependiendo de cómo fue el problema de P versus NP , podría representar "tiempo demostrablemente exponencial" o "tiempo previamente exponencial". [9]
Conceptos erróneos comunes
Los siguientes conceptos erróneos son frecuentes. [10]
- "Los problemas NP-completos son los problemas conocidos más difíciles". Dado que los problemas NP-completos están en NP, su tiempo de ejecución es como mucho exponencial. Sin embargo, se ha demostrado que algunos problemas requieren más tiempo, por ejemplo, la aritmética de Presburger . De algunos problemas, incluso se ha demostrado que nunca se pueden resolver en absoluto, por ejemplo, el problema de la detención .
- "Los problemas NP-completos son difíciles porque hay muchas soluciones diferentes". Por un lado, hay muchos problemas que tienen un espacio de solución igual de grande, pero que pueden resolverse en tiempo polinomial (por ejemplo, árbol de expansión mínimo ). Por otro lado, hay problemas NP con como máximo una solución que son NP-hard bajo reducción de tiempo polinomial aleatorio (ver el teorema de Valiant-Vazirani ).
- "Resolver problemas NP-completos requiere un tiempo exponencial". Primero, esto implicaría P ≠ NP, que aún es una cuestión sin resolver. Además, algunos problemas NP-completos en realidad tienen algoritmos que se ejecutan en superpolinomio, pero en tiempo subexponencial como O (2 √ n n ). Por ejemplo, los problemas de conjuntos independientes y conjuntos dominantes para gráficas planas son NP-completos, pero pueden resolverse en tiempo subexponencial usando el teorema del separador planar . [11]
- "Cada caso de un problema NP-completo es difícil". A menudo, algunos casos, o incluso la mayoría de los casos, pueden ser fáciles de resolver dentro del tiempo polinomial. Sin embargo, a menos que P = NP, cualquier algoritmo de tiempo polinómico debe ser incorrecto asintóticamente en más de muchas de las entradas exponencialmente polinomiales de cierto tamaño. [12]
- "Si P = NP, todos los cifrados criptográficos pueden romperse". Un problema de tiempo polinomial puede ser muy difícil de resolver en la práctica si el grado o las constantes del polinomio son lo suficientemente grandes. Por ejemplo, los cifrados con una longitud de clave fija, como Advanced Encryption Standard , pueden romperse en tiempo constante probando cada clave (y por lo tanto ya se sabe que están en P), aunque con la tecnología actual ese tiempo puede exceder la edad de el universo. Además, la seguridad basada en la teoría de la información proporciona métodos criptográficos que no se pueden romper incluso con una potencia informática ilimitada.
Propiedades
Al ver un problema de decisión como un lenguaje formal en alguna codificación fija, el NPC establecido de todos los problemas NP-completos no se cierra en:
- Unión
- intersección
- concatenación
- Estrella de Kleene
No se sabe si NPC está cerrado bajo complementación , ya que NPC = co-NPC si y solo si NP = co-NP , y si NP = co-NP es una pregunta abierta . [13]
Ver también
- Casi completo
- Gadget (informática)
- Teorema de ladner
- Lista de problemas NP-completos
- NP-duro
- P = problema NP
- Fuertemente NP-completo
- Vendedor ambulante (película de 2012)
Referencias
Citas
- ^ Cobham, Alan (1965). "La dificultad computacional intrínseca de las funciones". Proc. Lógica, metodología y filosofía de la ciencia II . Holanda Septentrional.
- ^ J. van Leeuwen (1998). Manual de Informática Teórica . Elsevier. pag. 84. ISBN 978-0-262-72014-4.
- ^ J. van Leeuwen (1998). Manual de Informática Teórica . Elsevier. pag. 80. ISBN 978-0-262-72014-4.
- ^ Garey, Michael 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 978-0-7167-1045-5. Señor 0519066 .
- ^ Agrawal, M .; Allender, E .; Rudich, Steven (1998). "Reducciones en la complejidad del circuito: un teorema de isomorfismo y un teorema de la brecha". Revista de Ciencias de la Computación y Sistemas . 57 (2): 127–143. doi : 10.1006 / jcss.1998.1583 . ISSN 1090-2724 .
- ^ Agrawal, M .; Allender, E .; Impagliazzo, R .; Pitassi, T .; Rudich, Steven (2001). "Reducir la complejidad de las reducciones". Complejidad computacional . 10 (2): 117-138. doi : 10.1007 / s00037-001-8191-1 . ISSN 1016-3328 .
- ^ Don Knuth , Tracy Larrabee y Paul M. Roberts, Escritura matemática Archivado el 27 de agosto de 2010 en Wayback Machine § 25, Notas de MAA No. 14 , MAA, 1989 (tambiénInforme técnico de Stanford , 1987).
- ^ Knuth, DF (1974). "Una propuesta terminológica". Noticias SIGACT . 6 (1): 12–18. doi : 10.1145 / 1811129.1811130 .
- ^ Ver la encuesta, o [1] Archivado 2011-06-07 en Wayback Machine .
- ^ Ball, Philip. "La computadora de ADN ayuda al vendedor ambulante" . doi : 10.1038 / news000113-10 .
- ^ Berna (1990) ; Deĭneko, Klinz y Woeginger (2006) ; Dorn y col. (2005) ; Lipton y Tarjan (1980) .
- ^ Hemaspaandra, LA; Williams, R. (2012). "Columna 76 de la teoría de la complejidad de las noticias de SIGACT". Noticias ACM SIGACT . 43 (4): 70. doi : 10.1145 / 2421119.2421135 .
- ^ Talbot, John; Galés, DJA (2006), Complexity and Cryptography: An Introduction , Cambridge University Press, pág. 57, ISBN 9780521617710,
La cuestión de si NP y co-NP son iguales es probablemente el problema abierto segunda más importante en la teoría de la complejidad, después de la P en función de la pregunta NP.
Fuentes
- Garey, MR ; Johnson, DS (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . Nueva York: WH Freeman. ISBN 978-0-7167-1045-5.Este libro es un clásico, desarrolla la teoría y luego cataloga muchos problemas NP-Complete.
- Cook, SA (1971). "La complejidad de los procedimientos de demostración de teoremas". Actas, Tercer Simposio Anual de ACM sobre Teoría de la Computación, ACM, Nueva York . págs. 151-158. doi : 10.1145 / 800157.805047 .
- Dunne, PE "Una lista comentada de problemas NP-completos seleccionados" . COMP202, Departamento de Ciencias de la Computación, Universidad de Liverpool . Consultado el 21 de junio de 2008 .
- Crescenzi, P .; Kann, V .; Halldórsson, M .; Karpinski, M .; Woeginger, G . "Un compendio de problemas de optimización de NP" . KTH, Estocolmo . Consultado el 24 de octubre de 2020 .
- Dahlke, K. "Problemas NP-completos" . Proyecto de referencia matemática . Consultado el 21 de junio de 2008 .
- Karlsson, R. "Lectura 8: Problemas NP-completos" (PDF) . Departamento de Ciencias de la Computación, Universidad de Lund, Suecia. Archivado desde el original (PDF) el 19 de abril de 2009 . Consultado el 21 de junio de 2008 .
- Sun, HM "La teoría de NP-completitud" . Laboratorio de seguridad de la información, Departamento de Ciencias de la Computación, Universidad Nacional Tsing Hua , ciudad de Hsinchu, Taiwán. Archivado desde el original (PPT) el 2009-09-02 . Consultado el 21 de junio de 2008 .
- Jiang, JR "La teoría de NP-completitud" (PPT) . Departamento de Ciencias de la Computación e Ingeniería de la Información, Universidad Nacional Central , Ciudad de Jhongli, Taiwán . Consultado el 21 de junio de 2008 .
- Cormen, TH ; Leiserson, CE ; Rivest, RL ; Stein, C. (2001). "Capítulo 34: NP: integridad". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 966–1021. ISBN 978-0-262-03293-3.
- Sipser, M. (1997). "Secciones 7.4–7.5 (NP-completitud, Problemas adicionales NP-completos)" . Introducción a la Teoría de la Computación . Publicación de PWS. págs. 248-271 . ISBN 978-0-534-94728-6.
- Papadimitriou, C. (1994). "Capítulo 9 (Problemas NP-completos)". Complejidad computacional (1ª ed.). Addison Wesley. págs. 181–218. ISBN 978-0-201-53082-7.
- Complejidad computacional de juegos y rompecabezas
- Tetris es difícil, incluso aproximado
- ¡Buscaminas es NP-completo!
- Berna, Marshall (1990). "Algoritmos exactos más rápidos para árboles Steiner en redes planas". Redes . 20 (1): 109-120. doi : 10.1002 / net.3230200110 ..
- Deĭneko, Vladimir G .; Klinz, Bettina; Woeginger, Gerhard J. (2006). "Algoritmos exactos para el problema del ciclo hamiltoniano en gráficos planares". Cartas de investigación operativa . 34 (3): 269–274. doi : 10.1016 / j.orl.2005.04.013 ..
- Dorn, Frederic; Penninkx, Eelko; Bodlaender, Hans L .; Fomin, Fedor V. (2005). "Algoritmos exactos eficientes en gráficos planares: explotando descomposiciones de rama de corte de esfera". Proc. XIII Simposio Europeo de Algoritmos (ESA '05) . Apuntes de conferencias en Ciencias de la Computación. 3669 . Springer-Verlag. págs. 95-106. doi : 10.1007 / 11561071_11 . ISBN 978-3-540-29118-3..
- Lipton, Richard J .; Tarjan, Robert E. (1980). "Aplicaciones de un teorema del separador plano". Revista SIAM de Computación . 9 (3): 615–627. doi : 10.1137 / 0209046 ..
Otras lecturas
- Scott Aaronson , NP-Complete Problems and Physical Reality , ACM SIGACT News, vol. 36, No. 1. (marzo de 2005), págs. 30–52.
- Lance Fortnow , El estado del problema P versus NP , Comun. ACM , vol. 52, núm. 9. (2009), págs. 78–86.