En la teoría de la complejidad computacional , NP ( tiempo polinomial no determinista ) es una clase de complejidad utilizada para clasificar los 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 por una máquina de Turing no determinista . [2] [Nota 1]
La primera definición es la base de la abreviatura NP; “ tiempo polinómico 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. [3]
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 pueden verificarse 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. Se cree ampliamente, pero no se ha demostrado, que P es menor que NP , en otras palabras, que existen problemas de decisión que no pueden resolverse en tiempo polinomial aunque sus soluciones puedan verificarse en tiempo polinomial. Los problemas más difíciles en NP se denominan problemas NP-completos . Un algoritmo que resuelva un problema de este tipo en tiempo polinomial también es capaz de resolver cualquier otro problema NP en tiempo polinomial. Si P fuera de hecho igual a NP, entonces existiría un algoritmo en tiempo polinomial para resolver problemas NP-completos y, por corolario, todos los problemas NP. [4]
La clase de complejidad NP está relacionada con la clase de complejidad co-NP , para la cual la respuesta "no" puede verificarse en tiempo polinomial. Si NP = co-NP o no es otra cuestión pendiente en la teoría de la complejidad. [5]
La clase de complejidad NP se puede definir en términos de NTIME de la siguiente manera:
donde es el conjunto de problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista en el 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 polinomios p y q , y una máquina de Turing determinista M , tales que
Muchos problemas de informática están contenidos en NP, como las versiones de decisión de muchos problemas de búsqueda y optimización.
Para explicar la definición de NP basada en el verificador, 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 números enteros suman cero, podemos crear un algoritmo que obtenga todos los subconjuntos posibles. A medida que aumenta el número de números enteros que introducimos en el algoritmo, tanto el número de subconjuntos como el tiempo de cálculo crecen exponencialmente.
Pero observe que si se nos da un subconjunto 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 realizar en tiempo polinómico 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 del 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; en caso contrario, entonces está en NP.
La versión de este problema con una respuesta "no" se enuncia de la siguiente manera: "dado un conjunto finito de números enteros, ¿todo 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 "no". La clase de problemas con tales verificadores para las respuestas "no" se denomina 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, son co-NP.
En alguna literatura al verificador se le denomina "certificador" y al testigo " certificado ". [2]
Equivalente a la definición basada en verificador es la siguiente caracterización: NP es la clase de problemas de decisión solucionables por 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 es reconocido por alguna máquina de Turing no determinista de tiempo polinomial con una condición de aceptación existencial , lo que significa que si y solo si alguna ruta de cálculo de conduce a un estado de aceptación. Esta definición es equivalente a la definición basada en verificador porque una máquina de Turing no determinista podría resolver un problema NP en tiempo polinomial seleccionando de manera no determinista un certificado y ejecutando el verificador en el certificado. De manera similar, si tal máquina existe, entonces naturalmente se puede construir un verificador de tiempo polinomial a partir de ella.
En este sentido, podemos definir dualmente a co-NP como la clase de problemas de decisión reconocibles por las 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 cuestión NP vs. co-NP como una pregunta sobre si las condiciones de aceptación existencial y universal tienen el mismo poder expresivo para la clase de máquinas de Turing no deterministas de tiempo polinomial.
NP es cerrado bajo unión , intersección , concatenación , estrella de Kleene e inversión . No se sabe si NP es cerrado bajo complemento (esta pregunta es la llamada pregunta "NP versus co-NP").
Debido a los muchos problemas importantes de esta clase, se han hecho 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, y que parecen requerir un tiempo superpolinómico . Si estos problemas no son decidibles en tiempo polinómico es una de las grandes preguntas abiertas en la ciencia 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" en NP. Si existe un algoritmo de tiempo polinómico para al menos uno de ellos, entonces existe un algoritmo de tiempo polinómico para todos los problemas en NP. Debido a esto, y debido a que la investigación dedicada no ha logrado encontrar un algoritmo polinómico para ningún problema NP-completo, una vez que se ha demostrado que un problema es NP-completo, esto se considera ampliamente como una señal de que es poco probable que exista un algoritmo polinómico para ese problema.
Sin embargo, en la práctica, en lugar de gastar recursos computacionales en buscar una solución óptima, a menudo se puede encontrar una solución suficientemente buena (pero potencialmente subóptima) en tiempo polinómico. Además, las aplicaciones reales de algunos problemas son más fáciles que sus equivalentes teóricos.
Las dos definiciones de NP como la clase de problemas solucionables por 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 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 demostrarlo, supongamos primero que tenemos un verificador determinista. Una máquina no determinista puede ejecutar el verificador de manera no determinista en todas las cadenas de prueba posibles (esto requiere solo una cantidad polinómica de 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 polinómicamente). Si alguna prueba es válida, alguna ruta la aceptará; si ninguna prueba es válida, la cadena no está en el lenguaje y la rechazará.
Por el contrario, supongamos que tenemos una TM no determinista llamada A que acepta un lenguaje dado L. En cada uno de sus pasos, que son polinómicamente numerosos, el árbol de cómputo de la máquina se ramifica en, como máximo, un número finito de direcciones. Debe haber al menos una ruta de aceptación, y la cadena que describe esta ruta es la prueba suministrada al verificador. El verificador puede entonces simular de manera determinista 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á.
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 recorra todas las cadenas de prueba y alimente cada una de ellas a un verificador de tiempo polinomial. Dado que una máquina de tiempo polinomial solo puede leer una cantidad polinomial de 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.
Los co-NP contienen aquellos problemas que tienen una prueba simple para ninguna instancia, a veces llamados contraejemplos. Por ejemplo, la prueba de primalidad es trivial en los co-NP, ya que uno puede refutar la primalidad de un entero simplemente proporcionando un factor no trivial. NP y co-NP juntos forman el primer nivel en la jerarquía polinómica , superior solo a P.
La NP se define utilizando únicamente máquinas deterministas. Si permitimos que el verificador sea probabilístico (no necesariamente una máquina BPP [6] ), obtenemos la clase MA solucionable utilizando un protocolo Arthur-Merlin sin comunicación de Arthur a Merlin.
La relación entre BPP y NP es desconocida: no se sabe si BPP es un subconjunto de NP , NP es un subconjunto de BPP o ninguno de los dos. Si NP está contenido en BPP , lo que se considera improbable ya que implicaría soluciones prácticas para problemas NP-completos , entonces NP = RP y PH ⊆ BPP . [7]
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 jerarquía temporal y del teorema de jerarquía espacial , y respectivamente son y .
En términos de la teoría de la complejidad descriptiva , la NP corresponde precisamente al conjunto de lenguajes definibles por la lógica existencial de segundo orden ( teorema de Fagin ).
La NP puede considerarse 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 de tiempo polinomial determinista que lo verifica. Es completa porque la cadena de prueba correcta hará que la acepte si existe una, y es sólida porque el verificador no puede aceptar si no existe una cadena de prueba aceptable.
Un resultado importante de la teoría de la complejidad es que la NP puede caracterizarse como los problemas que se pueden resolver mediante pruebas que se pueden comprobar probabilísticamente, donde el verificador utiliza 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 de NP descrito anteriormente puede reemplazarse por uno que simplemente "verifique al azar" algunos lugares en la cadena de prueba y, utilizando un número limitado de lanzamientos de moneda, puede determinar la respuesta correcta con alta probabilidad. Esto permite probar varios resultados sobre la dificultad de los algoritmos de aproximación .
Todos los problemas en P se denotan como . Dado un certificado para un problema en P , podemos ignorar el certificado y simplemente resolver el problema en tiempo polinomial.
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 a n ? [8]
Todo problema NP-completo está en NP.
El problema de satisfacibilidad booleana ( SAT ), donde queremos saber si una determinada fórmula en lógica proposicional con variables booleanas es verdadera o no para algún valor de las variables. [9]
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 consiste en 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 puede hacerse claramente en tiempo polinómico. Simplemente se suman 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:
Se puede pensar en cada suposición como si se " bifurcara " 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 única 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). [10] [8]
El problema del isomorfismo de subgrafos consiste en determinar si el grafo G contiene un subgrafo que es isomorfo al grafo H. [11 ]
