in

Thug lifeThug life GeekyGeeky ¡Pero qué c...!¡Pero qué c...! No me gustaNo me gusta Una moneríaUna monería

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

5 Comments

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ú

  2. Teorema de las mil reinas ? , ¿ resuelto ? , dicen que sí , pero algo falla . Si cogemos la formula y la aplicamos a un tablero de 10 reinas , veremos que se parece cómo un huevo a una castaña . El de 10 reinas tiene 724 combinaciones comprobadas y aplicando la formula salen 55 x 724 creo , es una diferencia abismal . dicen que es una tendencia …, pues sí , es cierto que hay algo de tendencia en este problema , ( problemón ), pues es el que nos va a descubrir : P= NP . Pero hay que calcular esa tendencia de una forma mas real , que siempre obtendremos números aproximados , pues los valores son muy elevados . tenemos un ordenador que nos va dando unos datos , ( Debe de llevar soluciones de tableros de 30- 40 reinas supongo ) , están perdiendo un tiempo precioso , suponiendo que programasen bien el ordenador , imagino que sí . Personalmente yo lo pondría a trabajar buscando las soluciones de los tableros 10-30-50-70-100 , ya que estamos hablando de 1000 reinas , con las impares es algo distinto , pero muy poco . Y después sabiendo cual es el dato que marca la tendencia , tendríamos un muy aproximado dato de las mil reinas , los datos exactos necesitaríamos un ordenador demasiado potente , ( imposible en muchos años ).
    Están muy bien los problemas de ordenador , pero si falla el conocimiento del problema , cómo funciona , pues eso , salen unas cifras muy altas y ahí están , ¿ quien las rebate ?. Por cierto es un problema rotacional de frecuencias , en las que tenemos que en unos tableros hay tres reinas exteriores y en otras cuatro , dos variables cuyas soluciones/tendencias nos pueden descubrir el tan ansiado P=NP . Haber si dando pistas hay algún matemático que aprueba el exámen . Buenas tardes a todos

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.

Bitport: Descarga torrents directo a Google Drive

Observa esta impresionante demo de animación facial