Clases de complejidad P y NP

La relación entre las clases de complejidad NP y P es una pregunta por primera vez formulada por el científico computacional Stephen Cook que la teoría de la complejidad computacional aún no ha podido responder. En esencia, la pregunta <<¿es P = NP completo?>> significa: <<Si es posible "verificar" rápidamente las soluciones de un problema (es decir, es un problema de tipo NP), ¿eso implica que también es posible "obtener" las respuestas con la misma rapidez? (es decir, es un problema de tipo P)>>, donde "rápidamente" significa "en tiempo polinómico".

Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP-completos, fue determinada por Pichard T. Ledner.​

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...). Este artículo se centrará en las clases P y NP.

Se considera el problema más importante en este campo, el Clay Mathematics Institute ha ofrecido un premio de un millón de dólares estadounidenses para quien 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 SÍ, 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 esta 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 SÍ/NO realmente no es importante; aún si se permiten respuestas más complicadas, el problema resultante resulta equivalente (o sea si FNP = FP).

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 determinista (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 determinista secuencial en un período de tiempo polinomial en funció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 determinista. 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.​

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 $c\cdot n^{k}$ 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 hacer la raíz cuadrada de 323 (+/-17.9722) redondear al entero menor en valor absoluto (17) e intentar dividir desde 17 a 2. 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, $\Sigma$.

Si existe una relación binaria $R\subset \Sigma ^{*}\times \Sigma ^{*}$ y un entero positivo $k$ tal que para todo $x\in \Sigma ^{*}$, se satisfacen las siguientes condiciones:

1. $x\in L\Leftrightarrow \exists y\in \Sigma ^{*}$ tal que $(x,y)\in R\;$ y $\left|y\right|\in \;O(\left|x\right|^{k})$ (O simboliza cota superior asintótica).
2. El lenguaje $L_{R}$=$\{x\#y:(x,y)\in R\}$ en $\Sigma \cup \{\#\}$ es decidible por una máquina de Turing en tiempo polinomial.

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

$\mathrm {COMPOSITE}$ = $\{x\in \mathbb {N} :x=pq\;{\text{para enteros}}\;p,q>1\}$

$R$ = $\{(x,y)\in \mathbb {N} \times \mathbb {N} :1<y<x\;;\;y\;{\text{divide a}}\;x\}$

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 $\mathrm {COMPOSITE} \in \mathbf {NP}$ si se verifica que COMPOSITE satisface la condición indicada previamente.

(Nota. Recientemente se demostró que COMPOSITE estaba dentro de P​)

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 NP es el Tiempo polinómico No uniforme (NP/Poly)[1]. Si un problema está en NP/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 P, no se comprueban las cadenas defectuosas que entran en la máquina de Turing, puesto que no es un verificador.

NP/poly es una clase grande que contiene casi todos los algoritmos prácticos, incluyendo todo el BPP. Si esta contiene a P, 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 (n³) 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 P en el sentido de que ellos son los que son más probable no se encuentren en P. Problemas P-difíciles son aquellos para los cuales cualquier problema en P puede ser reducido en tiempo polinómico. Los problemas de completitud P son aquellos problemas P-difícil que se encuentran en P. Por ejemplo, la versión de problema de decisión del problema del vendedor viajero es completamente P. Así ningún caso de ningún problema en P 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 NP, entonces P = NP. El problema del vendedor viajero es uno de muchos problemas P-completos. Si cualquier problema P-completo se encuentra contenido en NP, entonces se verificaría que P = NP. Desafortunadamente, se ha demostrado que muchos problemas importantes son P-completos y no se conoce la existencia de ningún algoritmo rápido para ellos.

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

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 P 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 máquina 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, está determinado por la existencia de una entrada válida. 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
• Problemas del milenio

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 Theor

y Resear

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-P 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, (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)

• Datos: Q746242