Este artículo puede resultar confuso o poco claro para los lectores . ( Julio de 2012 ) |
En la teoría de la complejidad computacional , un problema es NP-completo cuando:
El nombre "NP-completo" es la abreviatura de "completo en tiempo polinomial no determinista". En este nombre, "no determinista" se refiere a las 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 estar asociada con un conjunto de soluciones de longitud polinómica, la validez de cada una de las cuales puede probarse rápidamente (en tiempo polinómico ), [2] de modo que la salida para cualquier entrada sea "sí" si el conjunto de soluciones no está vacío y "no" si está vacío. La clase de complejidad de los problemas de esta forma se llama NP , una abreviatura de "tiempo polinómico no determinista". Se dice que un problema es NP-duro si todo en NP puede transformarse en él en tiempo polinómico aunque no esté en NP. Un problema es NP-completo si está tanto en NP como NP-duro. Los problemas NP-completos representan los problemas más difíciles en NP. Si algún problema NP-completo tiene un algoritmo de tiempo polinómico, todos los problemas en NP lo tienen. El conjunto de problemas NP-completos a menudo se denota por NP-C o NPC .
Aunque la solución de un problema NP-completo se puede verificar "rápidamente", no se conoce ninguna forma de encontrar una solución rápidamente. Es decir, el tiempo necesario para resolver el problema utilizando cualquier algoritmo conocido aumenta rápidamente a medida que crece el tamaño del problema. En consecuencia, determinar si es posible resolver estos problemas rápidamente, llamado el problema P versus NP , es uno de los problemas fundamentales sin resolver en la informática actual.
Si bien no se ha descubierto un método para calcular las soluciones de los problemas NP-completos, los informáticos y los programadores aún se enfrentan con frecuencia a problemas NP-completos. Los problemas NP-completos suelen abordarse mediante métodos heurísticos y algoritmos de aproximación .
Los problemas NP-completos están en NP , el conjunto de todos los problemas de decisión cuyas soluciones pueden verificarse en tiempo polinomial; NP puede definirse de manera equivalente como el conjunto de problemas de decisión que pueden resolverse 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. [ cita requerida ]
No se sabe si todos los problemas en NP pueden resolverse rápidamente; esto se llama el problema P versus NP . Pero si cualquier problema NP-completo puede resolverse rápidamente, entonces todos los problemas en NP pueden resolverse, porque la definición de un problema NP-completo establece que cada problema en NP debe ser rápidamente reducible a cualquier 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. [ cita requerida ]
Un problema de decisión es NP-completo si: [ cita necesaria ]
Se puede demostrar que está en NP demostrando que una solución candidata a puede verificarse en tiempo polinomial.
Téngase en cuenta que un problema que satisface la condición 2 se dice que es NP-duro , independientemente de que satisfaga o no la condición 1. [4]
Una consecuencia de esta definición es que si tuviéramos un algoritmo de tiempo polinomial (en una UTM o cualquier otra máquina abstracta equivalente a Turing ) para , podríamos resolver todos los problemas en NP en tiempo polinomial.
El concepto de NP-completitud 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 intenso debate entre los científicos informáticos sobre si los problemas NP-completos se podían resolver en tiempo polinómico en una máquina de Turing determinista . John Hopcroft llevó a todos los presentes en la conferencia a un consenso de que la cuestión de si los problemas NP-completos se pueden resolver en tiempo polinómico debería posponerse para su resolución en una fecha posterior, ya que nadie tenía pruebas formales de sus afirmaciones en un sentido u otro. [ cita requerida ] Esto se conoce como "la cuestión de si P = NP".
Nadie ha podido determinar de manera concluyente si los problemas NP-completos son de hecho solucionables en tiempo polinómico, lo que convierte a este en uno de los grandes problemas sin resolver de las matemáticas . El Instituto Clay de Matemáticas ofrece una recompensa de un millón de dólares ( Premio del Milenio ) a quien tenga una prueba formal de que P=NP o de que P≠NP. [5]
La existencia de problemas NP-completos no es obvia. El teorema de Cook-Levin establece que el problema de satisfacibilidad booleano es NP-completo, estableciendo así que tales problemas existen. En 1972, Richard Karp demostró que varios otros problemas también eran NP-completos (ver los 21 problemas NP-completos de Karp ); por lo 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 se habían demostrado que eran NP-completos; muchos de estos problemas están recopilados en Garey & Johnson (1979).
La forma más sencilla de demostrar que un nuevo problema es NP-completo es demostrar primero que es NP y luego reducir a él algún problema NP-completo conocido. Por lo tanto, resulta útil conocer una variedad de problemas NP-completos. La lista siguiente contiene algunos problemas conocidos que son NP-completos cuando se expresan como problemas de decisión.
A la derecha se muestra un diagrama de algunos de los problemas y las reducciones que se suelen utilizar para demostrar su carácter NP-completo. En este diagrama, los problemas se reducen de abajo hacia arriba. Nótese que este diagrama es engañoso como descripción de la relación matemática entre estos problemas, ya que existe una reducción en tiempo polinómico entre dos problemas NP-completos cualesquiera; pero indica dónde ha sido más fácil demostrar esta reducción en tiempo polinómico.
A menudo, hay solo una pequeña diferencia entre un problema en P y un problema NP-completo. Por ejemplo, el problema de 3-satisfacibilidad , una restricción del problema de satisfacibilidad booleano, sigue siendo NP-completo, mientras que el problema de 2-satisfacibilidad, ligeramente más restringido, está en P (específicamente, es NL-completo ), pero el problema de 2-sat. máx., ligeramente más general, es nuevamente NP-completo. Determinar si un grafo se puede colorear con 2 colores está en P, pero con 3 colores es NP-completo, incluso cuando se restringe a grafos planares . Determinar si un grafo es un ciclo o es bipartito es muy fácil (en L ), pero encontrar un subgrafo máximo bipartito o de 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.
Un ejemplo interesante es el problema del isomorfismo de grafos , el problema de la teoría de grafos que consiste en determinar si existe un isomorfismo de grafos entre dos grafos. Dos grafos son isomorfos si uno puede transformarse en el otro simplemente renombrando los vértices . Consideremos estos dos problemas:
El problema de isomorfismo de subgrafos es NP-completo. Se sospecha que el problema de isomorfismo de grafos no está en P ni en NP-completo, aunque sí está en NP. Este es un ejemplo de un problema que se considera difícil , pero que no se considera NP-completo. Esta clase se denomina problemas NP-intermedios y existe si y solo si P≠NP.
En la actualidad, todos los algoritmos conocidos para problemas NP-completos requieren un tiempo de entrada superpolinomial . El problema de cobertura de vértices tiene [6] para algunos 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:
Un ejemplo de un algoritmo heurístico es un algoritmo de coloración voraz subóptimo 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 coloración de gráficos . Cada vértice es una variable, se dibujan bordes 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 una cantidad bastante grande de registros de propósito general, incluso un enfoque heurístico es efectivo para esta aplicación.
En la definición de NP-completo dada anteriormente, el término reducción se utilizó en el significado técnico de una reducción de muchos a uno en tiempo polinomial .
Otro tipo de reducción es la reducción de Turing en tiempo polinómico . Un problema es reducible en tiempo polinómico a un problema de Turing si, dada una subrutina que se resuelve en tiempo polinómico, se puede escribir un programa que llame a esta subrutina y la resuelva en tiempo polinómico. Esto contrasta con la reducibilidad de muchos a 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á más pequeño 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 la 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 logarítmica de espacio. Dado que cada cálculo que se puede hacer en el espacio logarítmico también se puede hacer en tiempo polinomial, se deduce que si hay una reducción de muchos-uno en el espacio logarítmico, entonces también hay una reducción de muchos-uno en tiempo polinomial. Este tipo de reducción es más refinada que las reducciones de muchos-uno en tiempo polinomial más habituales y nos permite distinguir más clases como P-completo . Si bajo estos tipos de reducciones cambia la definición de NP-completo sigue siendo un problema abierto. Todos los problemas NP-completos conocidos actualmente son NP-completos bajo reducciones del espacio logarítmico. Todos los problemas NP-completos conocidos actualmente siguen siendo NP-completos incluso bajo reducciones mucho más débiles, como reducciones y reducciones. Se sabe que algunos problemas NP-completos, como SAT, son completos incluso bajo proyecciones de tiempo polilogarítmico. [7] Sin embargo, se sabe que las reducciones AC 0 definen una clase estrictamente más pequeña que las reducciones de tiempo polinomial. [8]
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". Informa que introdujeron el cambio en las pruebas de galerada para el libro (de "polinomio-completo"), de acuerdo con los resultados de una encuesta que había realizado en la comunidad de informática teórica . [9] Otras sugerencias hechas en la encuesta [10] incluyeron " hercúleo ", "formidable", el "duro" de Steiglitz en honor a Cook y el acrónimo "PET" de Shen Lin, que significaba "tiempo probablemente exponencial", pero que dependiendo de la dirección en que se desarrollara el problema P versus NP , podría significar "tiempo demostrablemente exponencial" o "tiempo previamente exponencial". [11]
Los siguientes conceptos erróneos son frecuentes: [12]
Al considerar un problema de decisión como un lenguaje formal en alguna codificación fija, el conjunto NPC de todos los problemas NP-completos no está cerrado bajo:
No se sabe si NPC está cerrado bajo complementación , ya que NPC = co-NPC si y solo si NP = co-NP , y dado que NP = co-NP es una pregunta abierta . [16]
de si NP y co-NP son iguales es probablemente el segundo problema abierto más importante en la teoría de la complejidad, después de la cuestión P versus NP.