En las matemáticas existen lo que se llaman problemas abiertos. Son problemas para los que se sabe que hay una solución, aunque nadie haya dado con ella todavía. Quizás el problema abierto (hasta hace poco) más conocido para el público general es el Último Teorema de Fermat:
No hay numeros enteros positivos x, y, z tales que xn + yn=zn, donde n es un número entero mayor que 2.
Desde que Pierre de Fermat enunció este teorema en 1637, nadie fue capaz de demostrarlo hasta 1994, y durante mucho tiempo fue uno de los problemas abiertos más conocidos del mundo de las matemáticas. Curiosamente, el Último Teorema de Fermat es de escaso interes teorico (en el sentido de que tanto si es cierto como si no, el teorema no tiene importantes repercusiones prácticas). Una de las cosas que he aprendido este año es que los matemáticos adoran a Pierre de Fermat no por su último teorema, sino por el Pequeño Teorema de Fermat, un teorema de gran utilidad (por ejemplo, es una de las bases del algoritmo criptográfico RSA).
Pues bien, en informática también hay muchos de estos problemas abiertos. Eso sí, a mi siempre me ha fascinado más el hecho de que hay problemas para los que se ha demostrado que nunca se podrá encontrar una solución. Por ejemplo, está demostrado que es imposible elaborar un algoritmo que, dado cualquier programa P, decida si P entrará en un bucle infinito en algún momento de su ejecución (si crees que te estoy engañando, ya estás leyendote el anexo del artículo Si Turing levantara la cabeza…).
Pero bueno, me desvío del tema: los problemas abiertos. Todo esto lo comento porque nuestro profesor de Algoritmos plantea como desafio a los alumnos la resolución de ciertos problemas abiertos. Lo siento mucho, pero eso es algo por lo que ya no paso. Bastante me atormenta la asignatura de Algoritmos como para además ponerme la capa de Super-Algoritmo-Man para luchar contra problemas en los que durante años han fracasado algunas de las mentes más brillantes de las matemáticas. Eso sí, en nuestra clase hay bastantes cerebrines que sí están por la labor… y resulta que durante la asignatura, dos alumnos han resuelto un problema abierto cada uno. Cagate lorito.
Sin entrar en demasiados detalles, uno de los alumnos ha descubierto la cota inferior de la complejidad de un problema clásico de algoritmia (relacionado con la detección de monedas falsas entre monedas genuinas). Descubrir la ‘cota inferior de la complejidad’ de un problema es un logro acojonante, porque quiere decir que has descubierto que un problema nunca podrá resolverme de manera más eficiente que la dada por la cota inferior. Para que nos enteremos: si un problema tiene como entrada n elementos (p.ej. n números) y la cota inferior es de n3, eso significa que ese problema nunca podrá resolverse en menos de n3 pasos (esta explicación omite muchos detalles, pero es para que me entendais todos… los más entendidos ya sabrán que me estoy refiriendo a la notación Big-Oh).
Otro de los alumnos ha cogido un problema cuyo mejor algoritmo conocido requiere n2 pasos, y ha encontrado un algoritmo que requiere sólo n pasos. También un logro interesante, aunque desde un punto de vista teorico no es tan acojonante como encontrar una cota inferior.
Pues ya veis el tipo de gente que deambula por esta universidad…
Por cierto, si esto de los problemas abiertos ha despertado vuestra curiosidad, os interesará saber cual es (con diferencia) el mayor problema abierto de la informática teorica: ¿P=NP? Esta sencilla formula trae de cabeza a buena parte de la comunidad de la informática teorica. Teneis más detalles aquí.
Últimos comentarios