El «problema de las 1000 reinas»: Gana un millón de dólares resolviendo el problema con un algoritmo

Imagina un tablero de ajedrez. Coloca dos reinas rivales en él, de modo tal que no se puedan atacar directamente. ¿Fácil? Bien, ahora repite el proceso sumando seis reinas más. Complicado, pero posible. Para finalizar, extiende el problema a tableros de cualquier tamaño, con cualquier número de reinas preestablecidas en ellos. El llamado «problema de las 1000 reinas» no es otra cosa que un ejemplo aislado para explicar un ejercicio mucho más complejo, «P versus NP», a un punto tal que el Instituto Clay de Matemáticas ofrece un millón de dólares por la primera demostración positiva.

Existe una competencia muy interesante a la que llaman «Los Siete Problemas del Milenio». Iniciada en el año 2000 por el Instituto Clay de Matemáticas, su objetivo es encontrar respuestas para siete problemas clásicos que se han «resistido» a una solución con el paso de los años. Hasta ahora, el único problema que recibió una demostración apropiada es el de la «Conjetura de Poincaré», desarrollada por el matemático ruso Grigori Perelman.

El instituto no dudó en ofrecerle un millón de dólares por su trabajo, pero Perelman lo rechazó, diciendo que su contribución no había sido mayor a la del matemático Richard S. Hamilton, quien había sugerido una solución previamente. Otro de los grandes problemas que el instituto desea ver resuelto es el famoso «P versus NP», y para tratar de entenderlo, lo más común es recurrir al ajedrez:

¿No ayudó? No te preocupes, a mí no me sirvió de mucho al principio. P versus NP es más complicado que tirar un par de reinas sobre un tablero, y su reputación de imposible está bien justificada. En términos muy relajados (y digo «relajados» con toda sinceridad) podemos decir que los problemas denominados P son fáciles de resolver y verificar con algoritmos, dentro de un «tiempo polinómico».

Por otro lado, los problemas NP son fáciles de verificar si su solución es correcta o no, mientras que llegar a ella demanda un gran tiempo y esfuerzo, con pérdidas notables de eficiencia. Ejemplos robustos de problemas NP son rompecabezas, el Sudoku, e incluso el Buscaminas. Ahora: ¿Qué sucedería si tú encuentras la clave para solucionar un problema NP en tiempo polinómico, con gran eficiencia?

Si logras eso comprobarás que no hay diferencias entre N y NP (N = NP), provocando que el Instituto Clay (y no la Universidad de St. Andrews como se ha repetido hasta el cansancio) arroje un millón de dólares en tu dirección, seguido probablemente por un premio Nobel, y el odio de expertos en criptografía alrededor del mundo. La mayoría de los expertos se inclina en favor de N ≠ NP, y a decir verdad muchas cosas dependen de ello (el antes mencionado cifrado es una). Pero si vas a intentarlo de todos modos… buena suerte. La necesitarás.