Clases de complejidad P y NP

Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP-completos en este caso fue determinada por Ladner.^[1]

La relación entre las clases de complejidad P y NP es una pregunta que aún no ha podido ser respondida por la teoría de la complejidad computacional. En esencia, la pregunta ¿es P = NP ? significa: si es posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO (donde "rápidamente" significa "en tiempo polinómico"), ¿es que entonces también se pueden "obtener" las respuestas rápidamente?

Los recursos comúnmente estudiados en complejidad computacional son:

– El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema.

– El espacio: mediante una aproximación a la cantidad de memoria utilizada para resolver el problema.

Los problemas se clasifican en conjuntos o clases de complejidad (L, NL, P, PCompleto, NP, NP-Completo, NP Duro...).Nosotros nos vamos a centrar en las clases P y NP.

Se lo considera el problema más importante en este campo--el Clay Mathematics Institute ha ofrecido un premio de $1 millón de dólares norteamericanos para quién desarrolle la primera demostración correcta.

Ejemplo

Consideremos, por ejemplo, el Problema de la suma de subconjuntos, que es un ejemplo de un problema fácil de verificar, pero cuya respuesta se cree (pero no ha sido demostrado) es difícil de calcular/hallar. Dado un conjunto de números enteros, ¿existe un subconjunto no vacío de ellos donde la suma de sus elementos es igual a 0? por ejemplo, ¿existe un subconjunto del conjunto {−2, −3, 15, 14, 7, −10} tal que la suma de sus elementos sea 0? La respuesta es SI, si bien puede llevar algún tiempo encontrar un subconjunto que satisface el requerimiento, según cual sea el tamaño del conjunto y subconjunto. Por otra parte, si alguien afirma que la respuesta es: «sí, porque la suma de {−2, −3, −10, 15} es igual a cero», entonces lo podemos comprobar en forma muy rápida y mediante unas pocas cuentas. Verificar que la suma del subconjunto es cero es un proceso mucho más rápido que encontrar el subconjunto. La información necesaria para verificar un resultado positivo/afirmativo es llamada un certificado. Por lo que podemos concluir que dado los certificados apropiados, es posible verificar rápidamente las respuestas afirmativas de nuestro problema (en tiempo polinomial) y es ésta la razón por la que el problema se encuentra en NP. Una respuesta a la pregunta P = NP sería determinar si en problemas del tipo SUMA-SUBCONJUNTO es tan fácil hallar la solución como verificarla. Si se encuentra que P no es igual a NP, ello significa que algunos problemas NP serían significativamente más difíciles de hallar su solución que verificar la misma. La respuesta sería aplicable a todo este tipo de problemas, no solo al ejemplo específico de SUMA-SUBCONJUNTO.

La restricción a problemas de tipo SI/NO realmente no es importante; aún si se permiten respuestas más complicadas, el problema resultante resulta equivalente (o sea si FP = FNP).

Contexto del problema

La relación entre las clases de complejidad P y NP es estudiada por la teoría de la complejidad computacional, la parte de la teoría de la computación que trata de los recursos requeridos durante el cálculo para resolver un problema dado. Los recursos más usuales son tiempo (¿cuántos pasos son necesarios para resolver un problema?) y espacio (¿cuánta memoria es necesaria para resolver un problema?).

En este tipo de análisis, se requiere un modelo de la computadora para la que desea estudiar el requerimiento en términos de tiempo. Típicamente, dichos modelos suponen que la computadora es determinística (dado el estado actual de la computadora y las variables de entrada, existe una única acción posible que la computadora puede tomar) y secuencial (realiza las acciones una después de la otra). Estas suposiciones son adecuadas para representar el comportamiento de todas las computadoras existentes, aún incluye a las máquinas con computación en paralelo.

En esta teoría, la clase P consiste de todos aquellos problemas de decisión que pueden ser resueltos en una máquina determinística secuencial en un período de tiempo polinomial en proporción a los datos de entrada. En la teoría de complejidad computacional, la clase P es una de las más importantes; la clase NP consiste de todos aquellos problemas de decisión cuyas soluciones positivas/afirmativas pueden ser verificadas en tiempo polinómico a partir de ser alimentadas con la información apropiada, o en forma equivalente, cuya solución puede ser hallada en tiempo polinómico en una máquina no-determinística. Por lo tanto, la principal pregunta aún sin respuesta en la teoría de la computación está referida a la relación entre estas dos clases:

¿Es P igual a NP?

En una encuesta realizada en el 2002 entre 100 investigadores, 61 creían que la respuesta era NO, 9 creían que la respuesta era SI, 22 no estaban seguros, y 8 creían que la pregunta podía ser independiente de los axiomas actualmente aceptados, y por lo tanto imposible de demostrar por el SI o por el NO.^[2]

Definiciones formales

Más precisamente, un problema de decisión es un problema que especifica una cadena de caracteres de datos de entrada y requiere como solución una respuesta por el SI o por el NO. Si existe un algoritmo (por ejemplo una máquina de Turing, o un programa en lenguajes Lisp o Pascal con memoria irrestricta) que es capaz de entregar la respuesta correcta para toda cadena de datos de longitud n en a lo sumo pasos, donde k y c son constantes independientes del conjunto de datos, entonces se dice que el problema puede ser resuelto en tiempo polinómico y lo clasificamos como perteneciente a la clase P. En forma intuitiva, consideramos que los problemas contenidos en P son aquellos que pueden ser resueltos en forma razonablemente rápida.

P suele ser la clase de problemas computacionales que son “eficientemente resolubles” o “tratables”, aunque haya clases potencialmente más grandes que también se consideran tratables, como RP Y BPP. Aunque también existen problemas en P que no son tratables en términos prácticos; por ejemplo, unos requieren al menos n^1000000 operaciones.

En forma intuitiva, se puede pensar que NP es un problema de decisión que es difícil de resolver si no se posee ningún otro dato o información adicional. Sin embargo, si se recibe la información adicional llamada un certificado, entonces el problema puede ser resuelto fácilmente. Por ejemplo, si se nos da el número 323 y se nos pregunta si 323 es un número factorizable, sin darnos ningún dato o información adicional, deberíamos analizar todos los números enteros positivos mayores que 2 pero menores que 323 para estudiar si alguno de ellos divide exactamente al 323. Sin embargo, si se nos da el número 17, podemos dividir 323 por 17 y rápidamente verificar que 323 es factorizable. El número 17 es llamado un certificado. El proceso de división para verificar que 323 es factorizable es en esencia una máquina Turing y en este caso es denominado el verificador para 323. Técnicamente se dice que el problema es fácil si se puede resolver en tiempo polinómico y que es difícil si se resuelve en tiempo exponencial. Formalmente, se define NP como un conjunto de lenguajes que satisfacen ciertas condiciones.

Sea L un lenguaje definido sobre un alfabeto finito, Σ.

Si existe una relación binaria y un entero positivo k tal que para todo , se satisfacen las siguientes condiciones:

(i) tal que y O.

(ii) El lenguaje L_R= en es decible.

Entonces, la máquina de Turing que decide L_R (que la llamaremos V) es llamada el Verificador para L y y es llamado el Certificado de membresía de x en L.

Finalmente, L se encuentra en NP "si y solo si" V corre en tiempo polinómico.

Ejemplo.

Sea COMPOSITE =

R =

Claramente, la pregunta de si un dado x es factorizable es equivalente a la pregunta sobre si x es un miembro de COMPOSITE. De hecho, se puede demostrar fácilmente que si se verifica que COMPOSITE satisface la condición indicada previamente.

(Nota. Recientemente se demostró que COMPOSITE estaba dentro de P^[3] )

La clase P

P es conocido por contener muchos problemas naturales, incluyendo las versiones de decisión de programa lineal, cálculo del máximo común divisor, y encontrar una correspondencia máxima.

Problemas notables en P

Algunos problemas naturales son completos para P, incluyendo la conectividad (o la accesibilidad) en grafos no dirigidos.

Una generalización de P es NP, que es la clase de lenguajes decidibles en tiempo polinómico sobre una máquina de Turing no determinista. De forma trivial, tenemos que P es un subconjunto de NP. Aunque no está demostrado, la mayor parte de los expertos creen que esto es un subconjunto estricto.

Aquí, EXPTIME es la clase de problemas resolubles en tiempo exponencial. De todas las clases mostradas arriba, sólo se conocen dos contenciones estrictas:

• P estrictamente está contenido en EXPTIME.
• L estrictamente está contenida en PSPACE.

Los problemas más difíciles en P son los problemas P-completos

Otra generalización de P es el Tiempo polinómico No uniforme (P/Poly)[1]. Si un problema está en P/poly, entonces puede solucionarse en un tiempo polinomial determinado el cual, dado una cadena, este solo depende de la longitud de la entrada. A diferencia de NP, no se comprueban las cadenas defectuosas que entran en la máquina de Turing, puesto que no es un verificador.

P/poly es una clase grande que contiene casi todos los algoritmos prácticos, incluyendo todo el BPP. Si esta contiene a NP, la jerarquía polinomial se colapsa con el segundo nivel. Por otra parte, esta también contiene algunos algoritmos poco prácticos, incluyendo algunos problemas no decidibles.

Propiedades

Los algoritmos de tiempo polinómico son cerrados respecto a la composición. Intuitivamente, esto quiere decir que si uno escribe una función con un determinado tiempo polinómico y consideramos que las llamadas a esa misma función son constantes y, de tiempo polinómico, entonces el algoritmo completo es de tiempo polinómico. Esto es uno de los motivos principales por los que P se considera una máquina independiente; algunos rasgos de esta máquina, como el acceso aleatorio, es que puede calcular en tiempo polinómico el tiempo polinómico del algoritmo principal reduciéndolo a una máquina más básica.

Las pruebas existenciales de algoritmos de tiempo polinómico

Se conoce que algunos problemas son resolubles en tiempo polinómico, pero no se conoce ningún algoritmo concreto para solucionarlos. Por ejemplo, el teorema Robertson-Seymour garantiza que hay una lista finita de los menores permitidos que compone (por ejemplo) el conjunto de los grafos que pueden ser integrados sobre un toroide; además, Robertson y Seymour demostraron que hay una complejidad O (n3) en el algoritmo para determinar si un grafo tiene un grafo incluido. Esto nos da una prueba no constructiva de que hay un algoritmo de tiempo polinómico para determinar si dado un grafo puede ser integrado sobre un toroide, a pesar de no conocerse ningún algoritmo concreto para este problema.

Ejemplos

Camino Mínimo: encontrar el camino mínimo desde un vértice origen al resto de los vértices.

Ciclo Euleriano: Encontrar un ciclo que pase por cada arco de un grafo una única vez.

La clase NP

La clase NP está compuesta por los problemas que tienen un certificado sucinto (también llamado testigo polinómico) para todas las instancias cuya respuesta es un SÍ. La única forma de que tengan un tiempo polinomial es realizando una etapa aleatoria, incluyendo el azar de alguna manera para elegir una posible solución, y entonces en etapas posteriores comprueba si esa solución es correcta.

En otras palabras, dada una solución para una cierta instancia, es posible comprobar que es válida en TIME (n^k). En el caso de SAT (Problema de satisfacibilidad booleana), dado una asignación de valores de verdad, se puede comprobar fácilmente si la fórmula es cierta o no. Una nMT puede "adivinar" la solución en O (n) y verificarla en tiempo polinómico.

Completitud de NP

Para analizar la pregunta P = NP, resulta muy útil el concepto de completitud NP. De manera informal, los problemas de completitud NP son los problemas más "difíciles" en NP en el sentido de que ellos son los que son más probable no se encuentren en P. Problemas NP-difíciles son aquellos para los cuales cualquier problema en NP puede ser reducido en tiempo polinómico. Los problemas de completitud NP son aquellos problemas NP-difícil que se encuentran en NP. Por ejemplo, la versión de problema de decisión del problema del vendedor viajero es completamente NP. Así ningún caso de ningún problema en NP puede ser transformado mecánicamente en una parte del problema del vendedor viajero, en tiempo polinómico. Por lo tanto, si el problema del vendedor viajero estuviera contenido en P, entonces P = NP. El problema del vendedor viajero es uno de muchos problemas NP-completos. Si cualquier problema NP-completo se encuentra contenido en P, entonces se verificaría que P = NP. Desafortunadamente, se ha demostrado que muchos problemas importantes son NP-completos y no se conoce la existencia de ningún algoritmo rápido para ellos.

La definición anterior de NP permite considerar de manera natural una clase de problemas complementarias. La co-NP está compuesta por los problemas que tienen un contraejemplo sucinto para todas las instancias cuya respuesta es NO.

Problema Clique

Denominamos Clique al siguiente problema:

Dado un grafo G y un entero k, ¿es posible encontrar un subgrafo de G completo de tamaño k?

• Claramente Clique pertenece a NP.

• Ahora deberemos hacer una reducción de SAT a NP.

• Supongamos que tenemos una fórmula en CNF:

C1 v C2 v . . . v Ck con n variables proposicionales.

Formaremos un grafo G con un nodo por cada literal que aparece en cada cláusula. Cada nodo está etiquetado con el literal que le dio origen. Agregaremos un arco entre un nodo etiquetado con l y un nodo etiquetado con l0 si y solo si:

– l y l0 están en cláusulas distintas.

– l no es el literal complementario de l.

Supongamos la siguiente fórmula: (x1 v x2 v ¬x3) ^ (¬x1 v ¬x3) ^ (x3 v x2). El grafo resultante queda como:

Ahora deberemos demostrar que G tiene un subgrafo completo de tamaño k si es satisfactible. Como todos los miembros del subgrafo pertenecen a cláusulas distintas, cualquier valuación que hace verdadero a todo literal en el subgrafo hace verdadera a la fórmula (recordemos que dos literales complementarios no pueden estar en un subgrafo completo). Si la fórmula es satisfecha, debe existir una valuación que haga verdaderos a al menos un literal en cada cláusula. Sean l1 pertenece a C1, l2 pertenece a C2, . . . , lk pertenece Ck estos literales. Notemos que no es posible que existan dos literales complementarios li y lj. Necesariamente, entonces, podemos construir arcos entre cada par de nodos en donde aparecen dichos literales siguiendo las reglas de construcción del grafo.

Ejemplos

Camino Máximo: Dados dos vértices de un grafo encontrar el camino (simple) máximo.

Ciclo Hamiltoniano: Ciclo simple que contiene cada vértice del grafo.

NP-Completo

Para abordar la pregunta de si P=NP, el concepto de la completitud de NP es muy útil. Informalmente, los problemas de NP-completos son los problemas más difíciles de NP, en el sentido de que son los más probables de no encontrarse en P. Los problemas de NP-completos son esos problemas NP-duros que están contenidos en NP, donde los problemas NP-duros son estos que cualquier problema en NP puede ser reducido a complejidad polinomial. Por ejemplo, la decisión del Problema del viajante de comercio es NP-completo, así que cualquier caso de cualquier problema en NP puede ser transformado mecánicamente en un caso del Problema del viajante de comercio, de complejidad polinomial. El Problema del viajante de comercio es de los muchos problemas NP-completos existentes. Si cualquier problema NP-completo estuviera en P, entonces indicaría que P=NP. Desafortunadamente, se sabe que muchos problemas importantes son NP-completos y a fecha de 2008, no se conoce ningún algoritmo rápido para ninguno de ellos. Basándonos solo en esta idea, no es obvio que exista un problema NP-completo. Un problema NP-completo trivial e ideado, se puede formular como: Dada una descripción de una máquina de Turing M que se detiene en tiempo polinómico, ¿existe una entrada de tamaño polinómico que M acepte? Es NP porque, dada una entrada, es simple comprobar si M acepta o no la entrada simulando M, es NP-duros porque el verificador para cualquier caso particular de un problema en NP puede ser codificado como una maquina M de tiempo polinomial que toma la solución para ser verificada como entrada. Entonces la pregunta de si el caso es o no un caso, esta determinado por la existencia de una entrada valida. El primer problema natural que se demostró ser NP-completo fue el Problema booleano de satisfacibilidad. Este resultado es conocido como el teorema de Cook-Levin; su prueba de que la satisfacibilidad es NP-completo contiene los detalles técnicos sobre máquinas de Turing y como se relacionan con la definición de NP. Sin embargo, después se demostró que el problema era NP-completo, la prueba por reducción, proporcionó una manera más simple de demostrar que muchos otros problemas están en esta clase. Así, una clase extensa de problemas aparentemente sin relación es reducible a otra, y son en este sentido el mismo problema.

Véase también

• Ciencias de la computación
• Teoría de la computación
• Teoría de autómatas
• Teoría de la computabilidad
• Teoría de la complejidad computacional

Referencias

1. ↑ R. E. Ladner "On the structure of polynomial time reducibility," J.ACM, 22, pp. 151–171, 1975. Corollary 1.1. ACM site.
2. ↑ William I. Gasarch (June 2002). «The P=?NP poll.». SIGACT News 33 (2):  pp. 34-47. doi:10.1145/1052796.1052804. http://www.cs.umd.edu/~gasarch/papers/poll.pdf. 
3. ↑ M. Agrawal, N. Kayal, N. Saxena. «Primes is in P».

Bibliografía

• A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. Automata, Languages, and Programming, Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A 31 (1981) 199-214.
• E. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994. D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory Research Worksh., 2000.
• Neil Immerman. Languages Which Capture Complexity Classes. 15th ACM STOC Symposium, pp.347-354. 1983.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). «Chapter 34: NP-Completeness». Introduction to Algorithms (Second Edition edición). MIT Press and McGraw-Hill. pp. 966–1021. ISBN 0-262-03293-7. 
• Christos Papadimitriou (1993). «Chapter 14: On P vs. NP». Computational Complexity (1st edition edición). Addison Wesley. pp. 329–356. ISBN 0-201-53082-1. 
• Apuntes de clase de la asignatura Análisis y Diseño de Algoritmos de la Escuela Superior de Infórmatica de Málaga

Enlaces externos

• The Clay Math Institute Millennium Prize Problems (en inglés)
• The Clay Math Institute Official Problem Description (pdf) (en inglés)
• Gerhard J. Woeginger. The P-versus-NP page. A list of links to a number of purported solutions to the problem. Some of these links state that P equals NP, some of them state the opposite. It's probable that all these alleged solutions are incorrect. (en inglés)
• Computational Complexity of Games and Puzzles
• Scott Aaronson's Complexity Zoo: P, NP (en inglés)
• Qeden, a wiki that aims to solve the Millennium Prize Problems (en inglés)
• Scott Aaronson's Shtetl Optimized blog: Reasons to believe, a list of justifications for the belief that P ≠ NP (en inglés)