Ecuación #49: ¿ P = NP ?

descripción de la imagen
El agente fue despedido por sus compañeros de trabajo. Foto EDH/ Mauricio Cáceres

Por Napoleón Cornejo

2019-01-19 8:21:24

Los algoritmos controlan nuestras vidas. Cuando manejamos con Waze o Google Maps, un algoritmo está calculando constantemente la mejor forma de llegar a nuestro destino tomando en cuenta el tráfico, distancia y ubicación. Al ordenar algo por Amazon, un algoritmo calcula la forma más óptima de transportar nuestra compra por la cadena logística. Y cuando viaja por avión, son algoritmos los que han calculado la agenda de los pilotos, la trayectoria de vuelo, los precios de los boletos y hasta cómo se venden las acciones de la aerolínea en la bolsa de valores.

¿Cómo empezó esta locura? Empezó mucho antes que existieran las computadoras. Las Ciencias de la Computación existen como una rama de las matemáticas que estudia los procedimientos rigurosos para calcular soluciones a problemas. Las computadoras son una herramienta, pero no siempre el objeto de su estudio. Aunque desde la antigua Grecia ya los pensadores tenían algunas nociones, en 1928 un matemático, David Hilbert, propuso un reto que daría origen formal a esta disciplina.

Lo que había propuesto se conoce como “El Problema de la Decisión”. Preguntaba si es posible diseñar un algoritmo que pueda tomar una serie de afirmaciones lógicas y responder una pregunta con un “sí” o un “no” adecuadamente. Por ejemplo, a la pregunta “¿existe un número más grande que todos los demás?”, el algoritmo debería poder partir desde los axiomas básicos de la matemática y ser capaz de responder “no”. Era un problema bastante abstracto y esotérico que casi ninguno de sus colegas quisieron tomar, hasta que llegó el joven Alan Turing.

Turing era un genio como pocos. En 1935, a la orilla de un río en Cambridge, Inglaterra, obtuvo la solución. Imaginó una máquina hipotética que leía afirmaciones (símbolos) continuamente de una cinta. Siguiendo instrucciones bien definidas (un algoritmo), escribe la respuesta. Si no existe una respuesta, se detiene. Hasta aquí bien. Pero luego se hizo la pregunta magistral: ¿puede una máquina de Turing saber si otra máquina de Turing va detenerse o responder? Con un espectacular rigor lógico, Alan Turing comprobó que es imposible construir una máquina así, respondiendo con eso el reto de Hilbert y estableciendo una incómoda realidad: existen problemas matemáticos que son “indecidibles”; es decir, que no existe forma de responderlos.

Todas las computadoras modernas son una implementación de la Máquina de Turing, con sus exactas mismas posibilidades y limitaciones, así que no pueden resolver todos los problemas. Pero de los que pueden responder, ¿son todos igual de complejos? No.

Esto fue evidente en los 70 cuando ya las computadoras empezaban a usarse en la práctica. Los programadores notaron que algunos problemas eran rápidos, como multiplicar u ordenar números. Pero había otros, que no importa que tanto se mejorara la computadora, seguían siendo lentos, como soluciones al ajedrez o encontrar números primos. Así que tipificaron la complejidad en dos clases: polinomiales (P) y polinomiales no-deterministas (NP).

Los problemas P son aquellos para los cuales encontrar una respuesta es rápido. Los problemas NP son aquellos que son muy complejos de resolver, pero cuya solución es muy fácil verificar. Multiplicar números es trivial (P). Encontrar los factores de un número no (NP), aunque la respuesta se corrobora fácilmente (multiplicando los factores).

Curiosamente, con el paso del tiempo se fueron encontrando algoritmos para los cuales algunos problemas NP se convertían en P (por ejemplo, encontrar números primos). Si pudo hacerse para algunos, ¿podrá eventualmente hacerse para todos? Este es uno de los problemas matemáticos más importantes de los últimos cien años:

¿P = NP?

La importancia de esta pregunta va más allá de las matemáticas. Muchas medicinas contra el cáncer funcionan por la forma en que interactúan con las proteínas de nuestro cuerpo. Pero calcular esa interacción es un problema NP. Si se lograra probar que P=NP, se abriría una puerta al diseño rápido de medicinas para muchas enfermedades. Es tan trascendental que el Instituto Clay de Matemáticas en EE. UU. lo considera uno de los siete problemas del milenio y por cuya solución ofrece un premio de un millón de dólares.

Solo que encontrar la respuesta es, irónicamente, un problema NP.

(Existen otras clases de problemas que son aún más complejos que la clase NP. Para más detalles, visite el sitio web: http://52ecuaciones.xyz).

Ingeniero Aeroespacial salvadoreño,
radicado en Holanda.

cornejo@52ecuaciones.xyz