in

Thug lifeThug life ¡Pero qué c...!¡Pero qué c...!

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

En realidad, el ajedrez no tiene nada que ver…


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.

Reportar

¿Qué te pareció?

Escrito por Lisandro Pardo

Comentarios

Leave a Reply
  1. Hallar una ecuación que genere todo tipo de tablero NXN es posible . Consta de 7 condicionales y puede resolver al menos una solución por tablero que va desde N=4 hasta N=infinito.
    Hasta ahora no se ha hallado una polinomial que resuelva con una reina colocada o 2 pero si he logrado para N menores a 25 con 2, 3, 4, 5 6, y 7 reinas soluciones para un tablero óptimo
    Asimismo he logrado unas mil soluciones para el tablero 1000×1000 aplicando métodos de clonaciòn, desplazamiento(derivación) y aplicando 3 propiedades fundamentales de formación distributiva de reinas en un tablero. Todo esto fundamentado en principios creados por mi persona. Espero pronto darlo a conocer todos mis descubrimientos acerca de este apasionante tema . Un saludo afectuoso desde Lima Perú

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

Loading…

0

Localingual: Base de datos para escuchar cómo se habla en todos los lugares del mundo

Cómo copiar más rápido archivos a un pendrive USB