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 polinómico mediante una máquina de Turing determinista , o alternativamente el conjunto de problemas que pueden resolverse en tiempo polinómico mediante una máquina de Turing no determinista. máquina . [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 suposición sobre la solución, que se genera de forma no determinista, mientras que la segunda fase consta de un algoritmo determinista que verifica si la suposición es una solución al problema. [3]
Es fácil ver que la clase de complejidad P (todos los problemas solucionables, deterministamente, en tiempo polinomial) está contenida en NP (problemas cuyas soluciones se pueden verificar en tiempo polinomial), porque si un problema se puede resolver 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, [Nota 2] los más difíciles de los cuales se denominan problemas NP completos . Un algoritmo que resuelva tal problema en tiempo polinomial también es capaz de 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 polinómico para resolver problemas NP completos y, por corolario, todos los problemas 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 polinómico. Si NP = co-NP es o no 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:
¿Dónde está el conjunto de problemas de decisión que pueden resolverse en el tiempo mediante una máquina de Turing no determinista ?
Alternativamente, NP se puede definir utilizando máquinas deterministas de Turing 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 , tal que
Muchos problemas informáticos están contenidos en NP, como versiones de decisión de muchos problemas de búsqueda y optimización.
Para explicar la definición de NP basada en verificadores, considere el problema de la suma de subconjuntos : supongamos que tenemos algunos números enteros , {−7, −3, −2, 5, 8}, y deseamos saber si algunos de estos los 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 nos dan 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 prueba o testigo de 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 suma de subconjuntos está en NP.
El ejemplo anterior se puede generalizar para cualquier problema de decisión. Dada cualquier instancia I del problema y el testigo W, si existe un verificador V de modo que dado el par ordenado (I, W) como entrada, V devuelve "sí" en tiempo polinómico si el testigo demuestra que la respuesta es "sí" o "no" en tiempo polinómico; de lo contrario, está en NP.
La versión de respuesta "no" de este problema se plantea 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 "no". La clase de problemas con tales verificadores para respuestas "no" se llama co-NP. De hecho, es una cuestión 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, al verificador se le llama "certificador" y al testigo, " certificado ". [2]
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 sólo si alguna ruta de cálculo 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 polinómico seleccionando de forma no determinista un certificado y ejecutando el verificador en el certificado. De manera similar, si existe una máquina de este tipo, entonces, naturalmente, se puede construir a partir de ella un verificador de tiempo polinomial.
Desde este punto de vista, 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 versus co-NP como si las condiciones de aceptación existencial y universal tienen el mismo poder expresivo para la clase de Turing no determinista de tiempo polinómico. máquinas.
NP está cerrado bajo unión , intersección , concatenación , estrella de Kleene e inversión . No se sabe si NP está cerrado bajo complemento (esta pregunta es la llamada pregunta "NP versus co-NP").
Debido a los muchos problemas importantes de 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 cuestiones 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 los problemas "más difíciles" de NP. Si hay un algoritmo de tiempo polinomial para uno solo 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 ampliamente como 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 algunos problemas en la vida real 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 (TM) no determinista 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 demostrar esto, supongamos primero 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 polinomiales 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, algún camino la 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 dado L. En cada uno de sus pasos polinómicos, el árbol de cálculo de la máquina se ramifica como máximo en 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 proporcionada al verificador. Luego, el verificador puede 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 ruta de aceptación y el verificador siempre la rechazará.
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 demostrar 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 sólo puede leer polinomialmente muchos bits, no puede utilizar más que el espacio polinómico, ni puede leer una cadena de prueba que ocupe más que el espacio polinómico (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 sin instancias , a veces llamados contraejemplos. Por ejemplo, la prueba de primalidad reside 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 polinómica , sólo superior a P.
NP se define utilizando únicamente 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.
Se desconoce la relación entre BPP y NP : 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 cual se considera poco probable 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 funciones es FNP .
Las únicas inclusiones estrictas conocidas provienen del teorema de la jerarquía temporal y del teorema de la jerarquía espacial , y respectivamente son y .
En términos de teoría descriptiva de la complejidad , la 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 determinista de tiempo polinomial que lo verifica. Está completo porque la cadena de prueba correcta hará que se acepte si la hay, 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 se puede caracterizar como los problemas que se pueden resolver mediante pruebas comprobables probabilísticamente en las que el verificador utiliza O(log n ) bits aleatorios y examina sólo 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 se puede reemplazar por uno que simplemente "verifique al azar" 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 .
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.
La versión del problema de decisión del problema de factorización de enteros : dados los números 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 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 las ciudades. Entonces la verificación se puede realizar 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:
Se puede pensar en cada suposición como " bifurcar " una nueva copia de la máquina de Turing para seguir cada uno de los caminos posibles, 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 ú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 a la versión de optimización, llamando a la versión de decisión repetidamente (un número polinómico de veces). [10] [8]
El problema del isomorfismo del subgrafo para determinar si el gráfico G contiene un subgrafo que es isomorfo al gráfico H. [11]
