NP (complejidad)

Diagrama de Euler para P, NP, NP-complete y NP-hard conjunto de problemas. Bajo el supuesto de que P ل NP, la existencia de problemas dentro de NP pero fuera de ambos P y NP-complete fue establecido por Ladner.

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 pruebas verificables en tiempo polinomial por una máquina de Turing determinista, o alternativamente el conjunto de problemas que pueden resolverse en tiempo polinomial tiempo por una máquina de Turing no determinista.

Una definición equivalente de NP es el conjunto de problemas de decisión solubles en tiempo polinomial por 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 forma no determinista, mientras que la segunda fase consiste en un algoritmo determinista que verifica si la conjetura es una solución al problema.

Es fácil ver que la clase de complejidad P (todos los problemas resolubles, determinísticamente, en tiempo polinomial) está contenida en NP (problemas cuyas soluciones se pueden verificar en tiempo polinomial), porque si un problema es resoluble en tiempo polinomial, entonces una solución también es verificable en tiempo polinomial simplemente resolviendo el problema. Pero NP contiene muchos más problemas, los más difíciles se llaman 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 problemas NP-completos y, como corolario, todos los problemas NP. Se cree ampliamente que este no es el caso.

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.

Definición formal

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

${displaystyle {Mathsf}=bigcup _{kin mathbb {N} {fn} {fn} {fn}} {fn}} {fn}} {\fn}} {fn}}} {fn}}}}} {fn}}} {fn}}}} {$

Donde ${displaystyle {mathsf {NTIME}(n^{k}}$ es el conjunto de problemas de decisión que puede ser resuelto por una máquina Turing no determinista en ${displaystyle O(n^{k}}$ tiempo.

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

• Para todos x y Sí., la máquina M se ejecuta en el tiempo p(en inglés)xSilencio) sobre la entrada ${displaystyle (x,y)}$.
• Para todos x dentro L, existe una cuerda Sí. de longitud q(en inglés)xtales que ${displaystyle M(x,y)=1}$.
• Para todos x no en L y todas las cuerdas Sí. de longitud q(en inglés)xTEN), ${displaystyle M(x,y)=0}$.

Antecedentes

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

Definición basada en verificadores

Para explicar la definición de NP basada en verificadores, considere el problema de la suma de subconjuntos: Supongamos que nos dan algunos números enteros, {−7, −3, −2, 5, 8}, y deseamos saber si algunos de estos números enteros suman cero. Aquí la respuesta es "sí", ya que los números enteros {−3, −2, 5} corresponden a la suma (−3) + (−2) + 5 = 0.

Para responder si algunos de los enteros suman cero podemos crear un algoritmo que obtenga todos los subconjuntos posibles. A medida que aumenta el número de enteros que ingresamos al algoritmo, tanto el número de subconjuntos como el tiempo de cálculo crecen exponencialmente.

Pero observe que si nos dan un subconjunto en particular, podemos verificar eficientemente si la suma del subconjunto es cero, sumando los 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 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 puede generalizarse para cualquier problema de decisión. Dado cualquier caso I del problema ${displaystyle Pi }$ y testigo W, si existe verificador V para que dado el par ordenado (I, W) como entrada, V devuelve "sí" en tiempo polinomio si el testigo demuestra que la respuesta es "sí" o "no" en tiempo polinomio de otra manera, entonces ${displaystyle Pi }$ está en NP.

La versión "sin"respuesta de este problema se establece como: "dado un conjunto finito de números enteros, ¿cada subconjunto no vacío tiene una suma distinta de cero?". La definición de NP basada en verificadores no requiere un verificador eficiente para las respuestas negativas. 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 alguna literatura, el verificador se denomina "certificador", y el testigo, "certificado".

Definición de máquina

Equivalente a la definición basada en el verificador es la siguiente caracterización: NP es la clase de problemas de decisión solvable por una máquina Turing no determinista que funciona en tiempo polinomio. Es decir, un problema de decisión ${displaystyle Pi }$ está en NP cada vez ${displaystyle Pi }$ es reconocido por algunos polinomio-tiempo no determinístico Máquina de tortuga ${displaystyle M}$ con una condición de aceptación existencial, significa que ${displaystyle win Pi }$ si y sólo si alguna ruta de cálculo ${displaystyle M(w)}$ conduce a un estado aceptado. Esta definición es equivalente a la definición basada en el verificador porque una máquina Turing no determinista podría resolver un problema NP en el tiempo polinomio seleccionando un certificado y ejecutando el verificador en el certificado. Del mismo modo, si tal máquina existe, entonces un verificador de tiempo polinomio puede ser construido naturalmente 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 polinomial 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 vs. co-NP como preguntando si las condiciones existenciales y de aceptación universal tienen el mismo poder expresivo para la clase de máquinas de Turing no deterministas de tiempo polinomial.

Propiedades

NP es cerrado bajo unión, intersección, concatenación, estrella Kleene e inversió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 la gran cantidad de problemas importantes en esta clase, se han realizado grandes esfuerzos para encontrar algoritmos de tiempo polinomial para problemas en NP. Sin embargo, sigue habiendo una gran cantidad de problemas en NP que desafían tales intentos y parecen requerir un tiempo superpolinomial. Si estos problemas no son decidibles en tiempo polinomial es una de las mayores preguntas abiertas en 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 el "más difícil" problemas en 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 podido encontrar un algoritmo polinomial para cualquier 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 un algoritmo polinomial para este problema. existir.

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 la vida real de algunos problemas son más fáciles que sus equivalentes teóricos.

Equivalencia de definiciones

Las dos definiciones de NP como la clase de problemas que se pueden resolver con una máquina de Turing no determinista (TM) en tiempo polinomial y la clase de problemas que se pueden verificar con una máquina de Turing determinista en tiempo polinomial son equivalentes. La prueba 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, supongamos que tenemos un verificador determinista. Una máquina no determinista puede simplemente ejecutar el verificador de manera no determinista en todas las cadenas de prueba posibles (esto requiere solo muchos pasos polinómicos 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 polinomialmente limitada).). Si alguna prueba es válida, algún camino aceptará; si ninguna prueba es válida, la cadena no está en el idioma y se rechazará.

Por el contrario, supongamos que tenemos una TM no determinista llamada A que acepta un lenguaje determinado L. En cada uno de sus muchos pasos polinómicos, 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 A de manera determinista, 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 uno puede verificar cualquier instancia del problema simplemente ignorando la prueba y resolviéndola. NP está contenido en PSPACE; para mostrar esto, basta con construir una máquina PSPACE que recorre todas las cadenas de prueba y alimenta cada una de ellas a un verificador de tiempo polinomial. Dado que una máquina de tiempo polinomial solo puede leer muchos bits polinómicos, no puede usar más que espacio polinomial, ni puede leer una cadena de prueba que ocupe más que 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 ninguna instancia, a veces llamados contraejemplos. Por ejemplo, la prueba de primalidad se encuentra trivialmente en co-NP, ya que uno 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 de polinomios, solo superior a P.

NP se define usando solo máquinas deterministas. Si permitimos que el verificador sea probabilístico (esto, sin embargo, no es necesariamente una máquina BPP), obtenemos la clase MA solucionable 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 el teorema de la jerarquía espacial, y respectivamente son ${displaystyle {Mathsf {NPsubsetneq.$ y ${displaystyle {Mathsf {NPsubsetneq.$.

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, donde el probador presenta el certificado de prueba y el verificador es una máquina de tiempo polinomial determinista que lo verifica. Está completo porque la cadena de prueba correcta hará que acepte si hay una, y es correcto 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 se puede caracterizar como los problemas que se pueden resolver mediante pruebas verificables probabilísticamente 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)). Más informalmente, esto significa que el verificador NP descrito anteriormente se puede reemplazar con uno que solo "verifica al azar" unos pocos lugares en la cadena de prueba, y el uso de un número limitado de lanzamientos de moneda puede determinar la respuesta correcta con alta probabilidad. Esto permite probar varios resultados sobre la dureza de los algoritmos de aproximación.

Ejemplos

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

Todos los problemas en P, denotado ${displaystyle {mathsf {subseteq No.$. Dado un certificado para un problema en P, podemos ignorar el certificado y resolver el problema en el tiempo polinomio.

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 hay una ruta que visite todas las ciudades con una distancia total menor que k.

Una prueba puede ser simplemente una lista de las 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 una ruta de este tipo de la siguiente manera:

• En cada ciudad visitará la próxima ciudad para visitar, hasta que haya visitado cada vértice. Si se atasca, se detiene inmediatamente.
• Al final verifica que la ruta que ha tomado ha costado menos que k dentro O()nHora.

Uno puede pensar en cada conjetura como "bifurcación" una nueva copia de la máquina de Turing para seguir cada uno de los caminos posibles hacia adelante, y si al menos una máquina encuentra una ruta de distancia menor que k, esa máquina acepta la entrada. (Equivalentemente, 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 en la versión de optimización llamando a la versión de decisión repetidamente (un número polinomial de veces).

La versión del problema de decisión del problema de factorización de enteros: dados los enteros n y k, ¿existe un factor f con 1 < f < k y f dividiendo n?

El problema de isomorfismo de subgrafo para determinar si el gráfico G contiene un subgrafo que es isomorfo al gráfico H.

El problema de satisfacibilidad booleana, en el que queremos saber si cierta fórmula en lógica proposicional con variables booleanas es verdadera o no para algún valor de las variables.