Maneras complicadas de ganar un millón (I): P vs NP

Los problemas del milenio

Existen siete problemas matemáticos conocidos como “los Problemas del Milenio”. Estos siete problemas fueron publicados por el Instituto Clay de Matematicas, anunciando además que premiaría su resolución con “la respetable suma” de un millón de dolares. Estos problemas fueron seleccionados por una comisión de expertos, quiénes valoraron que su resolución repercutirá en todos los ámbitos del progreso de la humanidad.

A día de hoy solo uno de estos problemas ha sido resuelto, la hipótesis de Poincaré (hablaremos de el).  Este es el primero de una serie de siete artículos que pretenden mostrar de la manera “más simple posible” (si es que existe una manera simple de presentarlos) cada uno de los siete Problemas del Milenio.

P vs NP

Solucionar no es lo mismo que verificar una posible solución. Bajo esta afirmación se sustenta todo el problema de P vs NP. Es una tortura calcular una raíz cuadrada a mano, por ejemplo calcular la raíz de 961, no obstante es inmediato elevar 31 al cuadrado y comprobar que efectivamente 312 = 961.

Entonces la pregunta que nos ocupa es la siguiente: ¿Las cuestiones que pueden verificarse en un tiempo razonable pueden también resolverse en un tiempo razonable?.

Hagamos otro ejercicio. Pensemos en un número y en un posible divisor exacto de ese número, es inmediato comprobar si el citado número es divisor exacto o no (simplemente realizando la división). Pero si nos pidiesen que dado un número encontrásemos sus factores primos, esto ya es otra cosa, sobretodo si ese número es muy grande. De hecho al dificultad de encontrar factores primos en números muy grandes es tal, que en eso se basa la criptografía actual, por ejemplo intenta descomponer el número 3.579.194 (está escogido con muy mala leche…, ver final del post).

Llamando P al conjunto de problemas solucionables en un tiempo razonable y NP al conjunto de problemas verificables en un tiempo razonable, el Instituto Clay propone el problema:

¿Es P = NP?

Pero ¿qué es un tiempo razonable?, o mejor dicho, ¿cuánto es un tiempo razonable?. Para entender esto tenemos que adentrarnos un poco en la teoría de algoritmos.

Algoritmos

Un algoritmo no es más que un conjunto de finito de reglas o instrucciones bien definidas para realizar una actividad. Por ejemplo para llenar un vaso de agua, este podría ser el algoritmo (es uno de muchos, esto se puede complicar tanto como se quiera):

  1. Coger la botella de agua.
  2. Quitar tapón de la botella.
  3. Coger un vaso vacío.
  4. Echar agua en el vaso hasta que este lleno, cuando el vaso este lleno, dejar de echar agua.
  5. Cerrar botella con el tapón.

Al final, casi todo lo que hacemos puede ser reducido a un algoritmo, la cosa es que este algoritmo puede o no ser eficiente, ya que (¡sorpresa!), un algoritmo depende de la “cantidad” de datos de entrada. Por decirlo de manera comprensible, en este caso, el tamaño importa.

Para ilustrar esto, imaginemos el siguiente problema:

Un determinado virus ha sido liberado en un laboratorio, infectando a un investigador, sin que él lo sepa. Ese mismo día tiene la cena de navidad con el resto de compañeros. El virus que ha contagiado se multiplica por 3 cada hora, es decir, afecta a otros tres individuos cada hora. Hasta el día siguiente nuestro colega investigador no se da cuenta de que ha sido infectado. Han pasado 24 horas. ¿A cuantas personas puede haber contagiado?

El investigador comienza sus cálculos del siguiente modo:

En la primera hora (t = 1) infectará a 3 personas, en la segunda (t = 2) el investigador podrá infectar a otras tres,pero además cada una de las 3 personas infectadas en la primera hora, tendrá la capacidad de infectar a otras tres, es decir, tenemos 9 posibles infectados solo por los tres infectados iniciales… A las 12 horas (t = 12) el número de infectados asciende a 531.441. Puesto que han pasado 24 horas desde la cena (t = 24) el número de personas potencialmente infectadas es de nada más ni nada menos que 282.429.536.481. Efectivamente, este tipo de crecimiento es exponencial, y enseguida nos percatamos de su rápido crecimiento (NOTA: esto es solo un ejemplo para ilustrar el crecimiento exponencial, la propagación de virus tiene en cuenta otros muchos factores).

N={ 3 }^{ t }

El tiempo de ejecución de algunos algoritmos crece de forma exponencial en función del “tamaño/longitud” de sus datos de entrada. Esto es un problema muy serio en computación, puesto a poco grande que sea nuestra cadena de entrada, el tiempo va creciendo cada vez más, hasta volverse inabordable en un tiempo razonable (podría tardar siglos en computarse el algoritmo), incluso para el ordenador más potente. Sin embargo, el crecimiento exponencial no es tan temible como el crecimiento combinatorio. La siguiente gráfica muestra tipos de crecimiento, podemos ver que el combinatorio es mayor que el exponencial:

Tipos_de_crecimiento

Por otra parte, el crecimiento combinatorio no es el mayor, puesto que es superado por:

f(n)={ n }^{ { n }^{ n } }

Y este a su vez vuelve a ser superado por:

f(n)={ n }^{ { n }^{ { n }^{ n } } }

Y mediante esta relación recursiva podríamos seguir así hasta el infinito.

Un problema dado puede ser resuelto mediante varios algoritmos. Por ejemplo el problema de ordenamiento puede ser resuelto en un tiempo O(n2) si consideramos el algoritmo Bubblesort y en un tiempo O(n·log(n)) si consideramos Merge sortPor tanto es inmediato ver que si queremos resolver el problema de ordenamiento lo más eficiente es utilizar merge sort, puesto que tiene un tiempo menor (número de pasos a seguir es del orden de n·log(n), donde n es la longitud de la cadena de entrada).

Definiciones “formales”

Y aquí viene la primera definición. ¿qué problemas consideramos tipo P? Básicamente en P están todos los problemas abordables en un tiempo polinómico, es decir, que pueden resolverse en un número de pasos del orden nk, siendo n la longitud de la cadena de entrada y k un número natural.

Esta definición es demasiado formal, ¿qué pasa si   k = 1.000?, el tiempo sería demasiado, aunque fuera polinómico. En la práctica se considera un tiempo polinómico todo aquel del orden O(n5), es decir, k = 5 (intuitivamente los programadores suelen buscar algoritmos mejores que O(n2)).

Y por supuesto,la definición de los problemas que están en NP. Los problemas clasificados como NP son aquellos en los que comprobar la repuesta nos llevaría un tiempo polinómico. Es decir, en este caso el algoritmo busca esa posible solución, no soluciona el problema per se. Dicho de otro modo, existe cierta influencia del azar, pues en algún momento del algoritmo habrá que considerar una solución potencial (y esta será tomada de manera más o menos aleatoria o bajo influencia del azar, en mayor o menor medida), y luego en etapas posteriores comprobar dicha solución. Si el tiempo de comprobación es polinómico, diremos que estamos ante un problema NP.

Una parte está clara, P esta contenido en NP, es decir,

P\subseteq NP

Puesto que podemos pensar en el algoritmo que resuelve un problema P en un tiempo polinómico también como el algoritmo de comprobación de resultado.

Y aquí volvemos al inicio del post, ¿es P = NP?, es decir, ¿Si podemos verificar las respuestas de un problema  del tipo SI/NO (problema de decisión) en un tiempo razonable (polinómico), también podemos obtener las respuestas en un tiempo razonable (polinómico)?

Los expertos en el tema son bastante escépticos, y se inclinan más por la posibilidad de que P no sea igual a NP. Y motivos para ello hay.

Consecuencias de P = NP

Supongamos por un instante que se demuestra que, efectivamente, P = NP. Los ordenadores podrían llevar a cabo tareas que hoy en día son inabordables, como que un ordenador juegue al ajedrez de forma perfecta (con la infinidad de combinaciones y jugadas posibles desde el estado inicial que eso conlleva), los computadores traducirían de forma simultánea y mejor que un traductor humano, la inteligencia artificial sería posible, pues podríamos realizar búsquedas masivas en tiempos polinómicos, etc.

Todos estos son algoritmos que en la actualidad son inabordables en un tiempo polinómico, como el problema del viajero, donde se quieren recorrer un conjunto de ciudades pasando por todas ellas y haciendo el menor recorrido en distancia posible. Parece que no hay otra solución que la fuerza bruta (comprobar todas las posibles soluciones).

En este sentido hay una implicación más de índole filosófica. Es mucho más difícil diseñar un avión que comprobar que está bien diseñado, al igual que es más sencillo comprobar que una demostración matemática es correcta que idear la propia demostración (que le pregunten a Andrew Wiles, quien tras 8 años de aislamiento resolvió el último teorema de Fermat, el cual llevaba sin resolverse desde 1637, prometo hablar de él en otra ocasión).

Esta sería la última frontera, donde perderíamos toda creatividad, algo que, si bien suena aterrador, según los expertos parece poco probable. Aunque quien sabe, tal vez las máquinas puedan superar algún día el Test de Turing…

PD: El número 3.579.194 no es primo, su descomposición en factores primos es 2·1.789.597.

Un comentario en “Maneras complicadas de ganar un millón (I): P vs NP

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s