NP (complejidad)

Problema sin resolver en informática

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

Más problemas sin resolver en informática

En la teoría de la complejidad computacional , NP ( tiempo polinomial no determinista ) es una clase de complejidad que se utiliza 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 por una máquina de Turing no determinista . ^{[ 2 ]}^{[ Nota 1 ]}

NP es el conjunto de problemas de decisión que pueden resolverse en tiempo polinomial mediante una máquina de Turing no determinista .
NP es el conjunto de problemas de decisión verificables en tiempo polinomial por una máquina de Turing determinista .

La primera definición es la base de la abreviatura NP; " no determinista , tiempo polinomial". Estas dos definiciones son equivalentes porque el algoritmo basado en la máquina de Turing consta de dos fases: la primera consiste en una suposición 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 suposición es una solución al problema. ^{[ 3 ]}

La clase de complejidad P (todos los problemas resolubles, de forma determinista, 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, aunque no está 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 resuelve un problema de este tipo en tiempo polinomial también puede resolver cualquier otro problema NP en tiempo polinomial. Si P fuera de hecho igual a NP, entonces existiría un algoritmo de tiempo polinomial para resolver problemas NP-completos y, por consiguiente, 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 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:

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

dónde ${\mathsf {NTIME}}(n^{k})$ es el conjunto de problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista en $O(n^{k})$ tiempo.

De forma equivalente, NP puede definirse utilizando máquinas de Turing deterministas como verificadores. Un lenguaje L pertenece a NP si y solo si existen polinomios p y q , y una máquina de Turing determinista M , tales que

Para todo x e y , la máquina M funciona en tiempo p (| x |) con entrada ⁠ $(x,y)$ .
Para todo x en L , existe una cadena y de longitud q (| x |) tal que $M(x,y)=1$ .
Para todo x que no está en L y todas las cadenas y de longitud q (| x |) , $M(x,y)=0$ .

Fondo

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.

Definición basada en verificadores

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

Para determinar si la suma de algunos números enteros es 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 observemos que si se nos da un subconjunto particular, podemos verificar eficientemente si la suma de sus elementos es cero, sumando los enteros que lo componen. Si la suma es cero, ese subconjunto es una prueba o evidencia de que la respuesta es "sí". Un algoritmo que verifica si la suma de los elementos de un subconjunto dado es cero es un verificador . Claramente, sumar los enteros de un subconjunto se puede hacer en tiempo polinomial, por lo que el problema de la suma de subconjuntos pertenece a NP.

El ejemplo anterior se puede generalizar para cualquier problema de decisión. Dado cualquier instancia I del problema $\Pi$ y el testigo W, si existe un verificador V tal 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 $\Pi$ está en NP.

La versión de este problema con respuesta negativa se plantea como: «dado un conjunto finito de enteros, ¿tiene cada subconjunto no vacío 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 dichos verificadores para las respuestas negativas se denomina co-NP. De hecho, es una cuestión abierta si todos los problemas de NP también tienen verificadores para las respuestas negativas y, por lo tanto, pertenecen a co-NP.

En algunos textos, al verificador se le llama "certificador" y al testigo " 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 resolubles por una máquina de Turing no determinista que se ejecuta en tiempo polinomial . Es decir, un problema de decisión $\Pi$ está en NP siempre $\Pi$ es reconocido por alguna máquina de Turing no determinista de tiempo polinomial $M$ con una condición de aceptación existencial , lo que significa que $w\in \Pi$ si y solo si alguna ruta de cálculo de $M(w)$ Esto conduce a un estado de aceptación. Esta definición es equivalente a la definición basada en el verificador, ya que una máquina de Turing no determinista podría resolver un problema NP en tiempo polinomial seleccionando un certificado de forma no determinista y ejecutando el verificador sobre dicho certificado. De manera similar, si existe tal máquina, entonces se puede construir de forma natural un verificador de tiempo polinomial a partir de ella.

En este sentido, podemos definir co-NP de forma dual 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 cuestión NP frente a 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.

Propiedades

El sintagma nominal (SN) es cerrado bajo unión , intersección , concatenación , estrella de Kleene e inversión . Se desconoce si el SN es cerrado bajo complemento (esta cuestión se conoce como la pregunta "SN versus co-SN").

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

Debido a la gran cantidad de problemas importantes en esta clase, se han realizado numerosos esfuerzos para encontrar algoritmos de tiempo polinomial para problemas en NP. Sin embargo, aún existen muchos problemas en NP que desafían tales intentos, ya que parecen requerir tiempo superpolinomial . Si estos problemas no son decidibles en tiempo polinomial es una de las mayores incógnitas en la informática (véase el problema P versus NP ("P = NP") para un análisis en profundidad).

Un concepto 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 existe un algoritmo de tiempo polinomial para al menos uno de ellos, entonces existe un algoritmo de tiempo polinomial para todos los problemas de NP. Debido a esto, y a que la investigación especializada no ha logrado encontrar un algoritmo polinomial para ningún problema NP-completo, una vez que se demuestra que un problema es NP-completo, esto se considera generalmente una señal de que es improbable que exista un algoritmo polinomial para dicho problema.

Sin embargo, en la práctica, en lugar de invertir recursos computacionales en la búsqueda de una solución óptima, a menudo se puede encontrar una solución suficientemente buena (aunque potencialmente subóptima) en tiempo polinomial. Además, las aplicaciones prácticas de algunos problemas son más sencillas que sus equivalentes teóricos.

Equivalencia de definiciones

Las dos definiciones de NP como la clase de problemas resolubles por una máquina de Turing no determinista (MT) 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 numerosos libros de texto, por ejemplo, en la sección 7.3 de « Introducción a la teoría de la computación» de Sipser .

Para demostrar esto, supongamos primero que tenemos un verificador determinista. Una máquina no determinista puede simplemente ejecutar el verificador de forma no determinista sobre todas las posibles cadenas de prueba (esto requiere solo un número polinomial de pasos, ya que puede elegir de forma 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, alguna ruta la aceptará; si ninguna prueba es válida, la cadena no pertenece al lenguaje y la rechazará.

Por el contrario, supongamos que tenemos una máquina de Turing no determinista llamada A que acepta un lenguaje L dado. En cada uno de sus pasos, que son polinomiales, el árbol de computación de la máquina se ramifica en un número finito de direcciones. Debe existir al menos una ruta de aceptación, y la cadena que describe esta ruta es la prueba que se proporciona al verificador. El verificador puede entonces simular A de forma determinista, siguiendo únicamente la ruta de aceptación, y verificar que acepta al final. Si A rechaza la entrada, no existe una ruta de aceptación, y el verificador siempre la rechazará.

Relación con otras clases

Inclusiones de clases de complejidad que incluyen P , NP, co-NP , BPP , P/poly , PH y PSPACE.

NP contiene todos los problemas de P , ya que se puede verificar cualquier instancia del problema simplemente ignorando la prueba y resolviéndola. NP está contenido en PSPACE ; para demostrarlo, basta con construir una máquina PSPACE que recorra todas las cadenas de prueba y las alimente 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 un espacio polinomial, ni puede leer una cadena de prueba que ocupe más que un espacio polinomial (por lo que no es necesario considerar pruebas más largas). NP también está contenido en EXPTIME , ya que el mismo algoritmo opera en tiempo exponencial.

co-NP incluye aquellos problemas que no tienen una demostración sencilla para ningún caso, a veces llamados contraejemplos. Por ejemplo, la prueba de primalidad pertenece trivialmente a co-NP, ya que se puede refutar la primalidad de un entero simplemente proporcionando un factor no trivial. NP y co-NP forman juntos el primer nivel de la jerarquía polinómica , superior solo a P.

NP se define utilizando únicamente máquinas deterministas. Si permitimos que el verificador sea probabilístico (sin embargo, esto no es necesariamente una máquina BPP ^{[ 6 ]} ), obtenemos la clase MA resoluble utilizando 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 , si NP es un subconjunto de BPP o si ninguna de las dos cosas. Si NP está contenido en BPP , lo cual 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: ${\mathsf {NP\subsetneq NEXPTIME}}$ y ${\mathsf {NP\subsetneq EXPSPACE}}$ .

Otras caracterizaciones

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

NP puede considerarse un tipo muy simple de sistema de prueba interactivo , donde el probador genera el certificado de prueba y el verificador es una máquina determinista de tiempo polinomial que lo comprueba. Es completo porque la cadena de prueba correcta hará que lo acepte si existe, y es sólido porque el verificador no puede aceptarlo si no hay una cadena de prueba aceptable.

Un resultado importante de la teoría de la complejidad es que los problemas NP se pueden caracterizar como aquellos que se resuelven mediante pruebas probabilísticas verificables, 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)). En términos más informales, esto significa que el verificador NP descrito anteriormente puede reemplazarse por uno que simplemente realiza comprobaciones aleatorias en algunos puntos de la cadena de prueba y, mediante un número limitado de lanzamientos de moneda, puede determinar la respuesta correcta con alta probabilidad. Esto permite demostrar varios resultados sobre la dificultad de los algoritmos de aproximación .

Ejemplos

PAG

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

Factorización de enteros

La versión de problema de decisión del problema de factorización de enteros : dados los enteros n y k , ¿existe un factor f tal que 1 < f < k y que divida a n ? ^[⁸^]

problemas NP-completos

Todo problema NP-completo pertenece a NP.

Satisfacibilidad booleana

El problema de satisfacibilidad booleana ( SAT ), donde queremos saber si una determinada fórmula en lógica proposicional con variables booleanas es verdadera o falsa para algún valor de las variables. ^{[ 9 ]}

vendedor viajero

La versión de decisión del problema del viajante pertenece a 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 consistir simplemente en una lista de las ciudades. De esta forma, la verificación se puede realizar en tiempo polinomial. Basta con sumar las entradas de la matriz correspondientes a las rutas entre las ciudades.

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

En cada ciudad que visita, "adivina" cuál es la siguiente que debe 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 un tiempo O ( n ).

Podemos imaginar cada intento como la creación de una nueva copia de la máquina de Turing para seguir cada uno de los caminos posibles. Si al menos una máquina encuentra una ruta con una distancia menor que k , esa máquina acepta la entrada. (De forma equivalente, esto puede considerarse como una única máquina de Turing que siempre acierta).

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

isomorfismo de subgrafos

El problema del isomorfismo de subgrafos ^consiste en determinar si un grafo $G$ contiene un subgrafo que es isomorfo al grafo $H.$ ^[¹¹ ]

Véase también

Máquina de Turing : modelo computacional que define una máquina abstracta.

Notas

↑ El tiempo polinomial se refiere a la rapidez con que crece el número de operaciones necesarias para un algoritmo, en relación con el tamaño del problema. Por lo tanto, es una medida de la eficiencia de un algoritmo.

Referencias

↑ Ladner, RE (1975). "Sobre la estructura de la reducibilidad en tiempo polinomial" . J. ACM . 22 : 151–171 . doi : 10.1145/321864.321877 . S2CID 14352974 . Corolario 1.1.
^ Kleinberg , Jon; Tardos, Éva (2006). Diseño de algoritmos (2ª ed.). Addison-Wesley. pag. 464 . ISBN 0-321-37291-3.
↑ Alsuwaiyel, MH: Algoritmos: Técnicas de diseño y análisis , pág. 283 .
↑ William Gasarch (junio de 2002). "La encuesta P=?NP" (PDF) . SIGACT News . 33 (2): 34–47 . doi : 10.1145/1052796.1052804 . S2CID 18759797. Consultado el 29 de diciembre de 2008 .
^ Kleinberg, Jon; Tardos, Éva (2006). Diseño de algoritmos (2ª ed.). Pearson/Addison-Wesley. pag. 496 . ISBN 0-321-37291-3.
↑ "Complexity Zoo:E" . Complexity Zoo . Archivado del original el 11 de noviembre de 2020. Consultado el 23 de marzo de 2018 .
↑ Lance Fortnow, Extrayendo la cuántica , 20 de diciembre de 2005
1 2 Wigderson, Avi. "P, NP y matemáticas: una perspectiva de complejidad computacional" (PDF) . Recuperado el 13 de abril de 2021 .
↑ Karp, Richard (1972). "Reducibilidad entre problemas combinatorios" (PDF) . Complejidad de los cálculos computacionales . págs. 85–103 . doi : 10.1007/978-1-4684-2001-2_9 . ISBN 978-1-4684-2003-6.
↑ Aaronson, Scott. "P=? NP" (PDF) . Consultado el 13 de abril de 2021 .
↑ Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . WH Freeman. ISBN 0-7167-1045-5.

Lecturas adicionales

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 polinomial, págs. 979 – 983.
Michael Sipser (1997). Introducción a la teoría de la computación . PWS Publishing. ISBN 0-534-94728-X.Secciones 7.3 – 7.5 (La clase NP, NP-completitud, Problemas NP-completos adicionales), págs. 241 – 271.
David Harel , Yishai Feldman . Algoritmia: El espíritu de la computación, Addison-Wesley, Reading, MA, 3.ª edición, 2004.

Enlaces externos

Zoológico de complejidad : NP
Introducción de American Scientist a la investigación tradicional y reciente sobre la teoría de la complejidad: "Algoritmos accidentales".

[3] El tiempo polinomial se refiere a la rapidez con que crece el número de operaciones necesarias para un algoritmo, en relación con el tamaño del problema. Por lo tanto, es una medida de la eficiencia de un algoritmo.

[1] Ladner, RE (1975). "Sobre la estructura de la reducibilidad en tiempo polinomial" . J. ACM . 22 : 151–171 . doi : 10.1145/321864.321877 . S2CID 14352974 . Corolario 1.1.

[kleinberg2006-2] Kleinberg , Jon; Tardos, Éva (2006). Diseño de algoritmos (2ª ed.). Addison-Wesley. pag. 464 . ISBN 0-321-37291-3.

[4] Alsuwaiyel, MH: Algoritmos: Técnicas de diseño y análisis , pág. 283 .

[poll-5] William Gasarch (junio de 2002). "La encuesta P=?NP" (PDF) . SIGACT News . 33 (2): 34–47 . doi : 10.1145/1052796.1052804 . S2CID 18759797. Consultado el 29 de diciembre de 2008 .

[kleinberg2006p496-6] Kleinberg, Jon; Tardos, Éva (2006). Diseño de algoritmos (2ª ed.). Pearson/Addison-Wesley. pag. 496 . ISBN 0-321-37291-3.

[7] "Complexity Zoo:E" . Complexity Zoo . Archivado del original el 11 de noviembre de 2020. Consultado el 23 de marzo de 2018 .

[8] Lance Fortnow, Extrayendo la cuántica , 20 de diciembre de 2005

[:0-9] 1 2 Wigderson, Avi. "P, NP y matemáticas: una perspectiva de complejidad computacional" (PDF) . Recuperado el 13 de abril de 2021 .

[10] Karp, Richard (1972). "Reducibilidad entre problemas combinatorios" (PDF) . Complejidad de los cálculos computacionales . págs. 85–103 . doi : 10.1007/978-1-4684-2001-2_9 . ISBN 978-1-4684-2003-6.

[11] Aaronson, Scott. "P=? NP" (PDF) . Consultado el 13 de abril de 2021 .

[12] Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . WH Freeman. ISBN 0-7167-1045-5.

[

[ 2 ]

[ Nota 1 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 9 ]

[ 10 ]

consiste