NP (complejidad)

Clase de complejidad utilizada para clasificar problemas de decisión.

Este artículo incluye una lista de referencias generales , pero permanece en gran parte sin verificar porque carece de suficientes citas en línea correspondientes . Ayude a mejorar este artículo introduciendo citas más precisas. ( Octubre de 2015 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

Problema no resuelto en informática :

${\displaystyle {\mathsf {P{\overset {?}{=}}NP}}}$

(más problemas sin resolver en informática)

Diagrama de Euler para un conjunto de problemas P , NP, NP-completo y NP-difícil . Bajo el supuesto de que P ≠ NP, Ladner estableció la existencia de problemas dentro de NP pero fuera de P y NP-completo . ^[1]

En la teoría de la complejidad computacional , NP ( tiempo polinomial no determinista ) es una clase de complejidad utilizada para clasificar problemas de decisión . NP es el conjunto de problemas de decisión para los cuales las instancias del problema , donde la respuesta es "sí", tienen demostraciones verificables en tiempo polinómico por una máquina de Turing no determinista . ^{[2] [Nota 1]}

Una definición equivalente de NP es el conjunto de problemas de decisión que se pueden resolver en tiempo polinomial mediante una máquina de Turing no determinista . Esta definición es la base de la abreviatura NP; " tiempo polinomial no determinista ". Estas dos definiciones son equivalentes porque el algoritmo basado en la máquina de Turing consta de dos fases, la primera de las cuales consiste en una conjetura sobre la solución, que se genera de manera no determinista, mientras que la segunda fase consiste en un algoritmo determinista que verifica si la suposición es una solución al problema. ^[3]

A los problemas de decisión se les asignan clases de complejidad (como NP) según los algoritmos más rápidos conocidos. Por lo tanto, los problemas de decisión pueden cambiar de clase si se descubren algoritmos más rápidos.

Es fácil ver que la clase de complejidad P (todos los problemas con solución determinista en tiempo polinomial) está contenida en NP (problemas donde las soluciones se pueden verificar en tiempo polinomial), porque si un problema se puede resolver en tiempo polinómico, entonces una solución es también verificable en tiempo polinomial simplemente resolviendo el problema. Pero NP contiene muchos más problemas, ^{[Nota 2]} los más difíciles de los cuales se denominan problemas NP-completos . Un algoritmo que resuelve un problema de este tipo en tiempo polinomial también puede resolver cualquier otro problema NP en tiempo polinomial. El problema más importante de P versus NP ("P = NP?"), pregunta si existen algoritmos de tiempo polinomial para resolver NP-completo y, como corolario, todos los problemas de NP. Se cree ampliamente que este no es el caso. ^[4]

La clase de complejidad NP está relacionada con la clase de complejidad co-NP para la cual la respuesta "no" se puede verificar en tiempo polinomial. Si NP = co-NP o no es otra cuestión pendiente en la teoría de la complejidad. ^[5]

Definición formal

La clase de complejidad NP se puede definir en términos de NTIME de la siguiente manera:

${\displaystyle {\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k}).}$

donde es el conjunto de problemas de decisión que una máquina de Turing no determinista puede resolver en el tiempo.${\displaystyle {\mathsf {NTIME}}(n^{k})}$${\displaystyle O(n^{k})}$

Alternativamente, NP se puede definir utilizando máquinas de Turing deterministas como verificadores. Un lenguaje L está en NP si y sólo si existen polinomios p y q , y una máquina de Turing determinista M , de tal manera que

• Para todos x y y , la máquina M se ejecuta en tiempo p (| x | ) en la entrada${\displaystyle (x,y)}$
• Para todo x en L , existe una cadena y de longitud q (| x |) tal que${\displaystyle M(x,y)=1}$
• Para todo x que no esté en L y todas las cadenas y de longitud q (| x |),${\displaystyle M(x,y)=0}$

Antecedentes

Muchos problemas de informática están contenidos en NP, como versiones de decisión de muchos problemas de búsqueda y optimización.

Definición basada en verificador

Para explicar la definición de NP basada en el verificador, considere el problema de la suma de subconjuntos : suponga que se nos dan algunos enteros , {−7, −3, −2, 5, 8}, y deseamos saber si algunos de estos los enteros suman cero. Aquí, la respuesta es "sí", ya que los enteros {−3, −2, 5} corresponden a la suma (−3) + (−2) + 5 = 0. La tarea de decidir si tal subconjunto con suma cero existe se llama problema de suma de subconjuntos .

Para responder si algunos de los números enteros se suman a cero, podemos crear un algoritmo que obtenga todos los subconjuntos posibles. A medida que aumenta el número de enteros que introducimos en el algoritmo, tanto el número de subconjuntos como el tiempo de cálculo aumentan exponencialmente.

Pero observe que si se nos da un subconjunto en particular, podemos verificar eficientemente si la suma del subconjunto es cero, sumando los números enteros del subconjunto. Si la suma es cero, ese subconjunto es una prueba o testigo de que la respuesta es "sí". Un algoritmo que verifica si un subconjunto dado tiene suma cero es un verificador . Claramente, la suma de los números enteros de un subconjunto se puede hacer en tiempo polinomial y, por lo tanto, el problema de la suma del subconjunto está en NP.

El ejemplo anterior se puede generalizar para cualquier problema de decisión. Dada cualquier instancia I de problema y testigo W, si existe un verificador V de modo que dado el par ordenado (I, W) como entrada, V devuelve "sí" en tiempo polinomial si el testigo prueba que la respuesta es "sí" o "no" en tiempo polinomial de lo contrario, entonces está en NP.${\displaystyle \Pi }$${\displaystyle \Pi }$

La versión "sin" respuesta de este problema se establece como: "dado un conjunto finito de enteros, ¿cada subconjunto no vacío tiene una suma distinta de cero?". La definición de NP basada en el verificador no requiere un verificador eficiente para las respuestas "no". La clase de problemas con tales verificadores para las respuestas "no" se llama co-NP. De hecho, es una pregunta abierta si todos los problemas en NP también tienen verificadores para las respuestas "no" y, por lo tanto, están en co-NP.

En algunas publicaciones, el verificador se denomina "certificador" y el testigo, el " certificado ". ^[2]

Definición de máquina

Equivalente a la definición basada en verificadores es la siguiente caracterización: NP es la clase de problemas de decisión que se pueden resolver mediante una máquina de Turing no determinista que se ejecuta en tiempo polinomial . Es decir, un problema de decisión está en NP siempre que sea ​​reconocido por alguna máquina de Turing no determinista de tiempo polinómico con una condición de aceptación existencial , lo que significa que si y solo si alguna ruta de cálculo de${\displaystyle \Pi }$${\displaystyle \Pi }$${\displaystyle M}$${\displaystyle w\in \Pi }$${\displaystyle M(w)}$conduce a un estado de aceptación. Esta definición es equivalente a la definición basada en el verificador porque una máquina de Turing no determinista podría resolver un problema de NP en tiempo polinómico seleccionando un certificado de manera no determinista y ejecutando el verificador en el certificado. De manera similar, si existe una máquina de este tipo, entonces, naturalmente, se puede construir un verificador de tiempo polinomial a partir de ella.

En este sentido, podemos definir co-NP dualmente como la clase de problemas de decisión reconocibles por máquinas de Turing no deterministas de tiempo polinómico con una condición de rechazo existencial. Dado que una condición de rechazo existencial es exactamente lo mismo que una condición de aceptación universal , podemos entender la pregunta NP frente a co-NP como preguntar si las condiciones de aceptación existencial y universal tienen el mismo poder expresivo para la clase de polinomios no-temporales. Máquinas de Turing deterministas.

Propiedades

NP está cerrado bajo unión , intersección , concatenación , estrella de Kleene y reversión . No se sabe si NP está cerrado bajo complemento (esta pregunta es la llamada pregunta "NP versus co-NP")

Por qué algunos problemas de NP son difíciles de resolver

Debido a los muchos problemas importantes de esta clase, se han realizado grandes esfuerzos para encontrar algoritmos de tiempo polinómico para problemas en NP. Sin embargo, sigue habiendo una gran cantidad de problemas en NP que desafían tales intentos, que parecen requerir un tiempo superpolinomial . Si estos problemas no son decidibles en tiempo polinomial es una de las mayores preguntas abiertas en la informática (consulte el problema P versus NP ("P = NP") para una discusión en profundidad).

Una noción importante en este contexto es el conjunto de problemas de decisión NP-completos , que es un subconjunto de NP y podría describirse informalmente como los problemas "más difíciles" de NP. Si hay un algoritmo de tiempo polinomial para incluso uno de ellos, entonces hay un algoritmo de tiempo polinomial para todos los problemas en NP. Debido a esto, y debido a que la investigación dedicada no ha logrado encontrar un algoritmo polinomial para ningún problema NP-completo, una vez que se ha demostrado que un problema es NP-completo, esto se considera una señal de que es poco probable que un algoritmo polinomial para este problema funcione. existe.

Sin embargo, en usos prácticos, en lugar de gastar recursos computacionales buscando una solución óptima, a menudo se puede encontrar una solución suficientemente buena (pero potencialmente subóptima) en tiempo polinomial. Además, las aplicaciones de algunos problemas en la vida real son más fáciles que sus equivalentes teóricos.

Equivalencia de definiciones

Las dos definiciones de NP como la clase de problemas que puede resolver una máquina de Turing no determinista (TM) en tiempo polinomial y la clase de problemas verificables por una máquina de Turing determinista en tiempo polinomial son equivalentes. La demostración se describe en muchos libros de texto, por ejemplo, Introducción a la teoría de la computación de Sipser , sección 7.3.

Para mostrar esto, primero suponga que tenemos un verificador determinista. Una máquina no determinista puede simplemente ejecutar de forma no determinista el verificador en todas las posibles cadenas de prueba (esto requiere solo polinomialmente muchos pasos porque puede elegir de manera no determinista el siguiente carácter en la cadena de prueba en cada paso, y la longitud de la cadena de prueba debe estar acotada polinomialmente). Si alguna prueba es válida, se aceptará alguna ruta; si ninguna prueba es válida, la cadena no está en el idioma y se rechazará.

A la inversa, suponga que tenemos una TM no determinista llamada A que acepta un lenguaje dado L. En cada uno de sus polinomios muchos pasos, el árbol de cálculo de la máquina se ramifica en un número finito de direcciones como máximo. Debe haber al menos una ruta de aceptación, y la cadena que describe esta ruta es la prueba proporcionada al verificador. El verificador puede entonces simular determinísticamente A, siguiendo solo la ruta de aceptación y verificando que acepta al final. Si A rechaza la entrada, no hay una ruta de aceptación y el verificador siempre rechazará.

Relación con otras clases

NP contiene todos los problemas en P , ya que se puede verificar cualquier instancia del problema simplemente ignorando la prueba y resolviéndola. NP está contenido en PSPACE; para mostrar esto, es suficiente construir una máquina PSPACE que recorra todas las cadenas de prueba y las envíe a un verificador de tiempo polinomial. Dado que una máquina de tiempo polinomial solo puede leer polinomialmente muchos bits, no puede usar más que el espacio polinomial, ni puede leer una cadena de prueba que ocupe más que el espacio polinomial (por lo que no tenemos que considerar pruebas más largas que esto). NP también está contenido en EXPTIME , ya que el mismo algoritmo opera en tiempo exponencial.

co-NP contiene aquellos problemas que tienen una prueba simple para ningún caso, a veces llamados contraejemplos. Por ejemplo, la prueba de primalidad se encuentra trivialmente en co-NP, ya que se puede refutar la primalidad de un número entero simplemente proporcionando un factor no trivial. NP y co-NP juntos forman el primer nivel en la jerarquía polinomial , más alto solo que P.

NP se define utilizando solo máquinas deterministas. Si permitimos que el verificador sea probabilístico (esto sin embargo, no es necesariamente una máquina BPP ^[6] ), obtenemos la clase MA que se puede resolver usando un protocolo Arthur-Merlin sin comunicación de Arthur a Merlin.

NP es una clase de problemas de decisión ; la clase análoga de problemas de función es FNP .

Las únicas inclusiones estrictas conocidas provienen del teorema de la jerarquía temporal y del teorema de la jerarquía espacial , y son respectivamente y .${\displaystyle {\mathsf {NP\subsetneq NEXPTIME}}}$${\displaystyle {\mathsf {NP\subsetneq EXPSPACE}}}$

Otras caracterizaciones

En términos de la teoría de la complejidad descriptiva , NP corresponde precisamente al conjunto de lenguajes definibles por la lógica existencial de segundo orden ( teorema de Fagin ).

NP puede verse como un tipo muy simple de sistema de prueba interactivo , en el que el probador presenta el certificado de prueba y el verificador es una máquina determinista de tiempo polinomial que lo verifica. Está completo porque la cadena de prueba correcta hará que se acepte si hay una, y es sólido porque el verificador no puede aceptar si no hay una cadena de prueba aceptable.

Un resultado importante de la teoría de la complejidad es que NP puede caracterizarse como los problemas que se pueden resolver mediante pruebas probabilísticamente verificables donde el verificador usa O (log n ) bits aleatorios y examina solo un número constante de bits de la cadena de prueba (la clase PCP (log n) , 1)). De manera más informal, esto significa que el verificador NP descrito anteriormente puede ser reemplazado por uno que simplemente "verifica" algunos lugares en la cadena de prueba, y usando un número limitado de lanzamientos de moneda se puede determinar la respuesta correcta con alta probabilidad. Esto permite probar varios resultados sobre la dureza de los algoritmos de aproximación .

Ejemplo

Esta es una lista de algunos problemas que se encuentran en NP:

Todos los problemas en P , denotados . Dado un certificado para un problema en P , podemos ignorar el certificado y simplemente resolver el problema en tiempo polinomial.${\displaystyle {\mathsf {P\subseteq NP}}}$

La versión de decisión del problema del viajante de comercio está en NP. Dada una matriz de entrada de distancias entre n ciudades, el problema es determinar si existe una ruta que visite todas las ciudades con una distancia total menor que k .

Una prueba puede ser simplemente una lista de ciudades. Entonces la verificación se puede hacer claramente en tiempo polinomial. Simplemente agrega las entradas de la matriz correspondientes a los caminos entre las ciudades.

Una máquina de Turing no determinista puede encontrar dicha ruta de la siguiente manera:

• En cada ciudad que visita "adivinará" la siguiente ciudad a visitar, hasta que haya visitado todos los vértices. Si se atasca, se detiene inmediatamente.
• Al final verifica que la ruta que ha tomado ha costado menos de k en O ( n ) tiempo.

Uno puede pensar en cada conjetura como " bifurcar " una nueva copia de la máquina de Turing para seguir cada uno de los posibles caminos hacia adelante, y si al menos una máquina encuentra una ruta de distancia menor que k , esa máquina acepta la entrada. (De manera equivalente, esto se puede considerar como una sola máquina de Turing que siempre adivina correctamente)

Una búsqueda binaria en el rango de distancias posibles puede convertir la versión de decisión de Travelling Salesman a la versión de optimización, llamando a la versión de decisión repetidamente (un número polinomial de veces). ^{[7] [8]}

La versión problema de decisión de la problema de factorización de enteros : números enteros dados n y k , ¿existe un factor f con 1 < f < k y f dividiendo n ? ^[8]

El problema isomorfismo subgrafo de determinar si el gráfico G contiene un subgrafo que es isomorfo a gráfico H . ^[9]

El problema de satisfacibilidad booleana , donde queremos saber si cierta fórmula en lógica proposicional con variables booleanas es verdadera para algún valor de las variables. ^[10]

Ver también

• máquina de Turing

Notas

1. tiempo polinomial se refiere a la rapidez con la que crece el número de operaciones que necesita un algoritmo, en relación con el tamaño del problema. Por tanto, es una medida de la eficacia de un algoritmo.
2. Bajo el supuesto de que P ≠ NP.

Referencias

1. Ladner, RE (1975). "Sobre la estructura de la reducibilidad del tiempo polinomial". J. ACM . 22 : 151-171. doi : 10.1145 / 321864.321877 . Corolario 1.1.
2. Kleinberg, Jon; Tardos, Éva (2006). Diseño de algoritmos (2ª ed.). Addison-Wesley. pag. 464 . ISBN 0-321-37291-3.
3. Alsuwaiyel, MH: Algoritmos: Técnicas de diseño y análisis , p. 283
4. William Gasarch (junio de 2002). "La encuesta P =? NP" (PDF) . Noticias SIGACT . 33 (2): 34–47. doi : 10.1145 / 1052796.1052804 . Consultado el 29 de diciembre de 2008 .
5. Kleinberg, Jon; Tardos, Éva (2006). Diseño de algoritmos (2ª ed.). pag. 496 . ISBN 0-321-37291-3.
6. "Complejidad zoológico: E - Complejidad zoológico" . ComplexZoo.uwaterloo.ca . Consultado el 23 de marzo de 2018 .
7. Aaronson, Scott. "P =? NP" (PDF) . Consultado el 13 de abril de 2021 .
8. Wigderson, Avi. "P, NP y matemáticas: una perspectiva de complejidad computacional" (PDF) . Consultado el 13 de abril de 2021 .
9. Garey, Michael R .; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . WH Freeman. ISBN 0-7167-1045-5.
10. Karp, Richard (1972). "Reducibilidad entre problemas combinatorios" (PDF) . Complejidad de los cálculos informáticos .

Lectura adicional

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sección 34.2: Verificación en tiempo polinómico, págs. 979–983. 
• Michael Sipser (1997). Introducción a la Teoría de la Computación . Publicación de PWS. ISBN 0-534-94728-X. Secciones 7.3–7.5 (La clase NP, NP-completitud, Problemas adicionales NP-completos), págs. 241–271.
• David Harel , Yishai Feldman . Algoritmos: El espíritu de la computación, Addison-Wesley, Reading, MA, 3ra edición, 2004.

Enlaces externos

• Complejidad Zoo : NP
• Cartilla de American Scientist sobre la investigación de la teoría de la complejidad tradicional y reciente: "Algoritmos accidentales"