P vs NP

Hola! Nueva semana, nuevo post. En esta ocasión seguiremos con las mates y con uno de los problemas del milenio, P vs NP. Como todos sabéis, los problemas del milenio son siete problemas matemáticos cuya resolución será premiada con un millón de dólares (un millón por cada problema), según anunció el Clay Mathematics Institute. A día de hoy, tan sólo uno de ellos ha sido resuelto. Se trata de la conjetura de Poincaré, demostrada con éxito por el matemático ruso Gregori Perelmán, si bien es cierto que rechazó el premio, al igual que la medalla Fields (equivalente al Nóbel, que como igualmente sabéis no se concede en el área matemática) Textualmente, “Grisha” como se le conoce, expuso lo siguiente para justificar su comportamiento: “No quiero estar expuesto como un animal en el zoológico. No soy un héroe de las matemáticas, ni siquiera soy tan exitoso. Por eso no quiero que todo el mundo me esté mirando …”

Actualmente vive en San Petersburgo, alejado del mundo exterior y de las matemáticas profesionales. Unas pocas personas en el mundo podrían  resolver la cuestión que plantearemos hoy. El es una de ellas.

Pero volvamos al tema que nos ocupa. Básicamente la cuestión consiste en decidir si la inclusión entre las clases de complejidad P y NP es estricta. Trataremos de explicar esto definiendo primeramente lo que significa P y NP.

• P= Problemas que se pueden RESOLVER en tiempo polinómico.
• NP= Problemas que se pueden COMPROBAR en tiempo polinómico.

O bien:

• P= Clase de complejidad que contiene problemas de decisión que se pueden resolver en un tiempo polinómico.
• NP= Clase de complejidad que contiene problemas de decisión que no se pueden resolver en un tiempo polinómico.

Igualmente, P=NP significa que por cada problema que tiene una solución eficiente y verificable, podríamos encontrar esa solución de una forma eficiente también.

Después de estas definiciones, analizaremos un poco más en profundidad todo lo expuesto. No obstante, os pondré un ejemplo muy esclarecedor. Si no habéis entendido lo que significa P y NP, con esto lo entenderéis. Si queremos asignar personas a 70 trabajos diferentes de forma que todas las personas tengan un trabajo y ninguna plaza quede vacante no sería difícil, para quien posea una mínima base matemática, establecer que la solución sería 70! Sin embargo la resolución de este número sería equivalente a un número del orden de 10 elevado a la centésima potencia, lo que ni en la edad del universo podría resolverse computacionalmente este problema.

Otro ejemplo más terrrenal sería el siguiente: ¿qué es más fácil, elevar un número al cuadrado (por ejemplo 15 x 15) o hayar la raíz cuadrada del resultado (raíz cuadrada de 225)? Todos sabríamos multiplicar quince por quince pero aseguraría que la mayor parte de los lectores no saben cómo realizar la raíz cuadrada de 225 de forma manual. Por lo tanto, llegamos a la conclusión que hayar la raíz cuadrada de un número es lento y laborioso, mientras que la operación inversa es todo lo contrario.

Siguiendo con esta línea, si nos piden que comprobemos si un número determinado X es la raíz cuadrada de Z podríamos resolverlo de dos formas:

• Calculando la raíz de Z y comparando con X (proceso lento y engorroso)
• Elevando X al cuadrado y comparando con Z (simple multiplicación X·X)

La conclusión que sacamos de este sencillo ejemplo es que en algunos problemas comprobar la solución es más eficiente que calcularla. La complejidad de la función “elevar al cuadrado” es más simple que calcular la raíz cuadrada. ¿Qué tiene que ver todo esto con P=NP? Pues bien, P es la clase de complejidad que contiene problemas de decisión que se pueden resolver en un tiempo polinómico. P contiene a la mayoría de problemas naturales, algoritmos de programación lineal, funciones simples,… Por ejemplo la suma de dos números naturales se resuelven en tiempo polinómico (para ser más exactos es de orden 2n) Entre los problemas que se pueden resolver en tiempo polinómico nos encontramos con diversas variedades, como los lineales (n), los cuadráticos (n2), los cúbicos (n3),… Volviendo al ejemplo principal llegamos a la conclusión que la función de elevar al cuadrado está contenida en la clase P.

La clase de complejidad NP contiene problemas que no pueden resolverse en un tiempo polinómico. Cuando se dice que un algoritmo no puede obtener una solución a un problema en tiempo polinómico siempre se intenta buscar otro procedimiento que lo consiga mejorar. Frente a los problemas contenidos en P, tienen métodos de resolución menos eficaces. Podemos ver que la operación de calcular la raíz cuadrada se encuentra contenida en esta clase.

Si nos resulta sencillo encontrar una solución para un determinado problema, sabemos comprobar si la solución es cierta (simplemente comparar), por lo que P es un subconjunto de la clase NP. La gran cuestión es si ocurre lo mismo a la inversa, es decir, si tengo un problema que sé comprobar fácilmente si un resultado es una solución, ¿sé calcular una solución sencillamente? ¿Todo problema se puede resolver en tiempo polinómico? Si alguien conoce la respuesta que se dirija al Instituto Clay y recoja su millón de dólares 🙂

Ahora que hemos expuesto la cuestión de una forma clara y definida, vamos a analizar detalladamente a P, NP y NP completos.

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.

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, sólo se conocen dos contenciones estrictas:

• P extrictamente está contenido en EXPTIME.
• L extrictamente está contenida en PSAPE.

EXPTIME (también llamada EXP) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(2^p(n)), donde p(n) es una función polinomial sobre n.

En teoría de la complejidad computacional, la clase PSPACE es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinomial () y tiempo ilimitado.

Otra generalización de P es el Tiempo polinómico No uniforme (P/Poly) 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, ésta también contiene algunos algoritmos poco prácticos, incluyendo algunos problemas no decidibles.

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.

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.

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.

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  más probablemente 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 complementarios. La co-NP está compuesta por los problemas que tienen un contraejemplo sucinto para todas las instancias cuya respuesta es NO.

En este punto me parece interesante enunciar el problema del viajante de comercio o por sus siglas en inglés TSP: Travelling Salesman Problem) La respuesta al problema es conocida, es decir se conoce la forma de resolverlo, pero sólo en teoría, en la práctica la solución no es aplicable debido al tiempo que computacionalmente se precisa para obtener su resultado.

Sean N ciudades de un territorio. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y minimice la distancia recorrida por el viajante. Es decir, encontrar una permutación P = {c₀,c₂,…,c_{n − 1}} tal que sea mínimo. La distancia entre cada ciudad viene dada por la matriz D: NxN, donde d[x, y] representa la distancia que hay entre la ciudad X y la ciudad Y.

La solución más directa es la que aplica la fuerza bruta: evaluar todas las posibles combinaciones de recorridos y quedarse con aquella cuyo trazado utiliza la menor distancia. El problema reside en el número de posibles combinaciones que viene dado por el factorial del número de ciudades (N!) y esto hace que la solución por fuerza bruta sea impracticable para valores de N incluso moderados con los medios computacionales actualmente a nuestro alcance. Por ejemplo, si un ordenador fuese capaz de calcular la longitud de cada combinación en un microsegundo, tardaría algo más de 3 segundos en resolver el problema para 10 ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y 77.146 años en resolver el problema para sólo 20 ciudades.

Las rutas posibles entre 12 ciudades son 479.001.600 combinaciones y el número de caminos individuales entre ciudades es el sumatorio desde 1 hasta 12-1, es decir, 66.

Se puede demostrar que el requerimiento de volver a la ciudad de partida no cambia la complejidad computacional del problema.

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 2011, 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.

Uff … vaya lío, ¿no? A trávés de este artículo prentendo haceros llegar la complejidad de un problema del milenio y de sus derivaciones a la vida actual, al mundo que nos rodea a cada uno de nosotros. He preferido escribir la parte “entendible” al principio y la parte “engorrosa” en una segunda instancia. Si lo hubiera hecho al revés, probablemente nadie hubiéramos entendido nada.

Como reflexión final, en palabras sencillas: ¿Para qué sirve esto? ¿Por qué es tan importante?

Los problemas de clase NP incluyen muchos problemas de patrones y optimización, que son de gran interés práctico, como por ejemplo la capacidad de determinar la colocación óptima de los transistores en un chip de silicio, el desarrollo de modelos precisos de previsión financiera, o el análisis del comportamiento del pliegue de proteínas en una célula.

El “problema P versus NP” plantea si estas dos clases son en realidad idénticas, es decir, si todos los problemas NP son también un problema P. Si P es igual a NP, todos los problemas NP contendrían un atajo oculto, lo que permitiría que los ordenadores encontrasen rápidamente soluciones perfectas. Pero si P no es igual a NP, entonces no existen dichos atajos, y la potencia de resolución de problemas de los ordenadores seguirá siendo fundamental y permanentemente limitada. La experiencia práctica sugiere abrumadoramente que P no es igual a NP. Sin embargo, hasta que alguien ofrezca una prueba matemática sólida, la validez de la hipótesis queda abierta.

Espero que os haya interesado este “problemilla” Si os creéis capaces de resolverlo, no sólo ganaréis fama y fortuna, sino que vuestro nombre quedará escrito en la Historia, y seréis recordados por futuras generaciones. Cualquier idea es buena y no olvidéis que la única forma de llegar al éxito es a través de los errores. Muchos de los grandes descubrimientos y avances tecnológicos actuales, han sido fruto de “experimentos fallidos”

La próxima semana hablaremos de otro de los problemas del milenio, probablemente el que más obsesiona a los matemáticos … “la hipótesis de Riemann”

Saludos y ser felices 🙂

Referencias de este artículo:

R. E. Ladner “On the structure of polynomial time reducibility,” J.ACM, 22, pp. 151–171, 1975. Corollary 1.1.

William I. Gasarch (June 2002). «The P=?NP poll.». SIGACT News 33 (2):  pp. 34-47.

M. Agrawal, N. Kayal, N. Saxena. «Primes is in P».