Problema abierto para la computación

Publicado el 13 de Octubre de 2020 | Matemáticas

¿Te acuerdas del efecto dos mil? Los ordenadores iban a sufrir un fallo de computación y se iban a revelar contra los humanos, al menos eso se rumoreaba, como los distintos apocalipsis que han ido profetizando distintos supuestos visionarios. Las profecías fallan más que una escopeta de feria, y menos mal, seríamos un mundo muy aburrido si se pudiese predecir lo que pasará miles de años más tarde. El único poder realmente predictor y profético es de la Astronomía, podemos calcular movimientos y órbitas por el cielo y proyectarlas en miles de años, con las ecuaciones necesarias fallaríamos tan solo en centímetros. Hilbert tampoco tuvo ese poder, ni siquiera basándonos en las décadas siguientes de su propuesta. En nuestro nuevo milenio, el tercero, y nuestro nuevo siglo, el XXI, también hemos tenido una lista para destacar los retos más relevantes de nuestros tiempos. En lugar de 23, tenemos tan solo 7 en este caso, problemas bien enunciados y concisos, que suponen los grandes problemas abiertos de nuestros tiempos.

El Instituto Clay de Matemáticas, una fundación sin ánimo de lucro de Cambridge (EEUU), anunció una lista de problemas matemáticos abiertos al empezar el siglo XXI, o el tercer milenio (según lo que quieras ver). La gran fama de estos problemas no viene únicamente por la selección de los problemas, sino por el premio que dotaron a la resolución de cualquiera de los problemas: un millón de dólares. Se conocen como los Problemas del Milenio, y sólo uno de los problemas está resuelto. ¿Entonces hay un matemático millonario? Bien pensado, pero no, lo rechazó, pero esa es otra historia. Vamos a hablar del primero de estos problemas: P versus NP

Es un problema de computación. Los ordenadores tienen, como los humanos, una limitación de espacio, llamado almacenamiento, y una limitación de tiempo, llamado tiempo de computación. El tiempo de computación es finito, el humano que lo programa no tiene un tiempo largo para esperar respuestas, y aunque lo tuviera, el propio material de la máquina se oxidaría. No hay nada infinito fuera de las Matemáticas. Realizar cálculos por ordenador es una ventaja. La computación ha cambiado y acelerado nuestro mundo, ahora somos capaces de comprobar resultados en cuestión de segundos y de interpretar conjuntos de datos antes inabordables. Pero hay límites. Hay algunas operaciones que computacionalmente tienen unos cálculos inviables. Digamos que tenemos una clase de complejidad de problemas llamada NP que 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. Si los mejoramos y conseguimos que el mismo problema sea computacionalmente viable, o resuelto en un tiempo polinómico, habremos conseguido pasarlo a la clase de complejidad P.

Pues bien, no se sabe si todos los problemas son NP, con un subgrupo de problemas P que pasan a ser resolubles en tiempos razonables, o todos en realidad son P y simplemente no sabemos hallar el algoritmo adecuado en muchos casos. Esto trae de cabeza a los programadores desde 1971, porque no saben si tienen o no la culpa de no saber dar respuesta a un problema. La complejidad de un problema consiste en sacar el mejor algoritmo que lo resuelva, pero cuando no sabes si hay respuesta o no, vaya desesperación…

Por Santiago García