NP-completitud

En la teoría de la complejidad computacional , los problemas NP-completos son los más difíciles de aquellos cuyas soluciones pueden verificarse rápidamente . Más precisamente, un problema es NP-completo cuando:

1. Es un problema de decisión , lo que significa que para cualquier dato de entrada, el resultado es "sí" o "no".
2. Cada entrada del problema se asocia con un conjunto de soluciones cortas (de longitud polinómica) , que pueden o no resolver válidamente la entrada. La salida es "sí" cuando al menos una de estas soluciones es válida, y "no" cuando ninguna lo es.
3. La validez de cada solución se puede verificar rápidamente (es decir, en tiempo polinomial ), y un algoritmo de búsqueda por fuerza bruta puede encontrar una solución válida (si existe) probando todas las soluciones posibles.
4. Este problema puede utilizarse para simular cualquier otro problema para el que podamos verificar rápidamente la validez de una solución. Por lo tanto, si pudiéramos encontrar rápidamente soluciones válidas para algún problema NP-completo (cuando existan), podríamos encontrar rápidamente soluciones válidas para cualquier otro problema en el que una solución dada pueda verificarse fácilmente.

Los problemas que cumplen los tres primeros criterios pertenecen a la clase NP , abreviatura de "no determinista de tiempo polinomial". 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 por fuerza bruta. El tiempo polinomial se refiere a un tiempo considerado "rápido" 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. Un problema que pertenece a NP y que además cumple el cuarto criterio se denomina "NP-completo". El término " completo " se refiere a la propiedad de poder simular todo en la misma clase de complejidad : si algún problema NP-completo tiene un algoritmo de tiempo polinomial, todos los problemas en NP lo tienen.

El conjunto de problemas NP-completos se suele denotar como NP-C o NPC .

Si bien la solución a un problema NP-completo puede verificarse "rápidamente", no existe un método conocido para encontrarla con rapidez. Es decir, el tiempo necesario para resolver el problema con cualquier algoritmo conocido aumenta rápidamente a medida que crece su tamaño. En consecuencia, determinar si es posible resolver estos problemas con rapidez, lo que se conoce como el problema P versus NP , es uno de los problemas fundamentales sin resolver en la informática actual.

Si bien aún no se ha descubierto un método para calcular rápidamente las soluciones a problemas NP-completos, los informáticos y programadores siguen encontrándose frecuentemente con este tipo de problemas. Los problemas NP-completos suelen abordarse mediante métodos heurísticos y algoritmos de aproximación .

Un problema de decisión${\displaystyle \scriptstyle C}$es NP-completo si:

1. ${\displaystyle \scriptstyle C}$está en NP, y
2. Cada problema en NP es reducible a${\displaystyle \scriptstyle C}$en tiempo polinomial. ^{[ 2 ] [ 3 ]}

${\displaystyle \scriptstyle C}$Se puede demostrar que está en NP demostrando que una solución candidata a${\displaystyle \scriptstyle C}$puede verificarse en tiempo polinomial.

Un problema de decisión que se puede resolver en tiempo polinomial pertenece a la clase P. Todos los problemas en P están necesariamente en NP. Sin embargo, no se ha demostrado que la clase NP sea realmente mayor que P. En otras palabras, aún no se sabe si existen problemas en NP que no estén en P. La cuestión de si las clases P y NP son iguales o no se conoce como el problema P versus NP . Una consecuencia de la definición de NP-completitud es que si tuviéramos un algoritmo de tiempo polinomial (en una UTM , o cualquier otra máquina abstracta equivalente a Turing ) para${\displaystyle \scriptstyle C}$, podríamos resolver todos los problemas en NP en tiempo polinomial.

Se dice que un problema es NP-difícil si todo lo que pertenece a NP puede transformarse en él en tiempo polinomial, aunque no pertenezca a NP. ^{[ 4 ]} Un problema es NP-completo si pertenece a NP y es NP-difícil. Por lo tanto, los problemas NP-completos son, en cierto sentido, los problemas más difíciles de NP.

El teorema de Cook-Levin establece que el problema de satisfacibilidad booleana es NP-completo, demostrando por primera vez la existencia de este tipo de problemas. En 1972, Richard Karp demostró que otros problemas también eran NP-completos (véase la lista de 21 problemas NP-completos de Karp ); por lo tanto, existe una clase de problemas NP-completos, además de la satisfacibilidad booleana. Desde estos resultados iniciales, se ha demostrado que miles de otros problemas son NP-completos mediante reducciones a partir de problemas previamente demostrados como NP-completos; muchos de estos problemas se recogen en Garey y Johnson (1979) .

La forma más sencilla de demostrar que un problema nuevo es NP-completo consiste primero en probar que pertenece a NP y, a continuación, reducirlo a un problema NP-completo conocido. Por lo tanto, es útil conocer diversos problemas NP-completos. La siguiente lista 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 usar para demostrar su NP-completitud. En este diagrama, los problemas se reducen de abajo hacia arriba. Cabe señalar que este diagrama puede resultar engañoso como descripción de la relación matemática entre estos problemas, ya que existe una reducción en tiempo polinomial entre cualquier par de problemas NP-completos; sin embargo, indica dónde ha sido más fácil demostrar esta reducción en tiempo polinomial.

A menudo, la diferencia entre un problema en P y un problema NP-completo es mínima. Por ejemplo, el problema de 3-satisfacibilidad , una restricción del problema de satisfacibilidad booleana, 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 max. 2-sat., ligeramente más general, también es 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 bipartito máximo o un subgrafo 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.

Actualmente, todos los algoritmos conocidos para problemas NP-completos requieren un tiempo superpolinomial en función del tamaño de la entrada.

Las siguientes técnicas pueden aplicarse 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 esté, como máximo, a un factor de la óptima.
• Restricción: Al restringir la estructura de la entrada (por ejemplo, a grafos planares), generalmente es posible obtener algoritmos más rápidos.
• Parametrización : En ocasiones, es posible encontrar algoritmos cuyos tiempos de ejecución son un polinomio del tamaño de la entrada multiplicado por una función superpolinómica de otro parámetro que describe la entrada. Estos algoritmos pueden ser rápidos, incluso para entradas grandes, cuando el parámetro está acotado.
• Heurística : Un algoritmo que funciona "razonablemente bien" en muchos casos, pero del que no hay pruebas de que sea siempre rápido y siempre produzca un buen resultado. A menudo se utilizan enfoques metaheurísticos .

En la definición de NP-completo dada anteriormente, el término reducción se utilizó en el sentido 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 polinomial . Un problema${\displaystyle \scriptstyle X}$es Turing-reducible en tiempo polinomial a un problema${\displaystyle \scriptstyle Y}$si, dada una subrutina que resuelve${\displaystyle \scriptstyle Y}$En tiempo polinomial, se podría escribir un programa que llame a esta subrutina y resuelva${\displaystyle \scriptstyle X}$en tiempo polinomial. 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 se define el análogo de NP-completo con reducciones de Turing en lugar de reducciones de muchos a uno, el conjunto de problemas resultante no será menor que NP-completo; es una cuestión abierta si será mayor.

Otro tipo de reducción que también se usa a menudo para definir la NP-completitud es la reducción muchos a uno en espacio logarítmico, que es una reducción muchos a uno que se puede calcular con solo una cantidad logarítmica de espacio. Dado que cada cálculo que se puede hacer en espacio logarítmico también se puede hacer en tiempo polinomial, se deduce que si hay una reducción muchos a uno en espacio logarítmico, entonces también hay una reducción muchos a uno en tiempo polinomial. Este tipo de reducción es más refinado que las reducciones muchos a 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 en espacio logarítmico. Todos los problemas NP-completos conocidos actualmente siguen siendo NP-completos incluso bajo reducciones mucho más débiles como${\displaystyle AC_{0}}$reducciones y${\displaystyle NC_{0}}$reducciones. Se sabe que algunos problemas NP-completos, como SAT, son completos incluso bajo proyecciones de tiempo polilogarítmicas. ^{[ 6 ]} Sin embargo, se sabe que las reducciones AC ⁰ definen una clase estrictamente más pequeña que las reducciones de tiempo polinomial. ^{[ 7 ]}

El concepto de NP-completitud se introdujo en 1971 (véase el teorema de Cook-Levin ), aunque el término NP-completo se introdujo posteriormente. En la conferencia STOC de 1971 , se produjo un acalorado debate entre los informáticos sobre si los problemas NP-completos podían resolverse en tiempo polinomial en una máquina de Turing determinista . John Hopcroft logró que todos los asistentes a la conferencia llegaran a un consenso: la cuestión de si los problemas NP-completos son resolubles en tiempo polinomial debía posponerse para abordarse más adelante, ya que nadie tenía pruebas formales que respaldaran sus afirmaciones.

El Instituto Clay de Matemáticas designó la cuestión P versus NP como uno de los siete Problemas del Premio del Milenio en 2000. ^{[ 8 ] [ 9 ]}

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 imprenta del libro (de "polinomialmente completo"), de acuerdo con los resultados de una encuesta que había realizado a la comunidad de la informática teórica . ^{[ 10 ]} Otras sugerencias hechas en la encuesta ^{[ 11 ]} incluyeron " hercúleo ", "formidable", "duro" de Steiglitz en honor a Cook, y el acrónimo de Shen Lin "PET", que significaba "tiempo probablemente exponencial", pero dependiendo de cómo se resolviera el problema P versus NP , podría significar " tiempo demostrablemente exponencial" o "tiempo previamente exponencial". ^{[ 12 ]}

Los siguientes conceptos erróneos son frecuentes. ^{[ 13 ]}

• Los problemas NP-completos son los problemas conocidos más difíciles. Dado que los problemas NP-completos pertenecen a NP, su tiempo de ejecución es, como máximo, exponencial. Sin embargo, se ha demostrado que algunos problemas requieren más tiempo, como por ejemplo la aritmética de Presburger . De algunos problemas, incluso se ha demostrado que nunca podrán resolverse, como por ejemplo el problema de la parada .
• Los problemas NP-completos son difíciles porque tienen muchísimas soluciones diferentes. Por un lado, hay muchos problemas con un espacio de soluciones igual de grande, pero que pueden resolverse en tiempo polinomial (por ejemplo, el árbol de expansión mínima ). Por otro lado, hay problemas NP con como máximo una solución que son NP-difíciles bajo reducción aleatoria en tiempo polinomial (véase el teorema de Valiant-Vazirani ).
• "Resolver problemas NP-completos requiere tiempo exponencial." En primer lugar, esto implicaría que P ≠ NP, lo cual sigue siendo una cuestión sin resolver. Además, algunos problemas NP-completos tienen algoritmos que se ejecutan en tiempo superpolinomial, pero subexponencial, como O(2 ^{√ n} n ). Por ejemplo, los problemas del conjunto independiente y del conjunto dominante para grafos planares son NP-completos, pero pueden resolverse en tiempo subexponencial utilizando el teorema del separador planar . ^{[ 14 ]}
• "Cada instancia de un problema NP-completo es difícil." A menudo, algunas instancias, o incluso la mayoría, pueden resolverse fácilmente en tiempo polinomial. Sin embargo, a menos que P=NP, cualquier algoritmo de tiempo polinomial debe ser asintóticamente incorrecto en más de un número polinomial de las entradas exponencialmente numerosas de un tamaño determinado. ^{[ 15 ]}
• 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 suficientemente grandes. Además, la seguridad basada en la teoría de la información proporciona métodos criptográficos que no pueden romperse ni siquiera con una capacidad de cálculo ilimitada.
• "Una computadora cuántica a gran escala sería capaz de resolver eficientemente problemas NP-completos." La clase de problemas de decisión que pueden ser resueltos eficientemente (en principio) por una computadora cuántica tolerante a fallos se conoce como BQP. Sin embargo, no se cree que BQP contenga todos los problemas NP, y si no los contiene, entonces no puede contener ningún problema NP-completo. ^{[ 16 ]}

Si se considera un problema de decisión como un lenguaje formal en alguna codificación fija, el conjunto NPC de todos los problemas NP-completos no es cerrado bajo:

• unión
• intersección
• concatenación
• Estrella Kleene

No se sabe si NPC es cerrado bajo complementación , ya que NPC = co-NPC si y solo si NP = co-NP , y dado que NP = co-NP es una cuestión abierta . ^{[ 17 ]}

• Casi completo
• Dispositivo (informática)
• Teorema de Ladner
• Lista de problemas NP-completos
• NP-difícil
• Problema P = NP
• Fuertemente NP-completo
• El viajante de comercio (película de 2012)