El Problema de las 1000 Reinas: Un algoritmo agobiante, impracticable y realizable

Por Noé Gabriel Portes Gil Bermeo

Es posible que, comprendiendo a la Mecánica Cuántica y logrando hacer funcionar de manera enteramente eficaz un computador cuántico, se logre llegar a la resolución de un problema que, con un algoritmo que al ser humano le puede resultar agobiante, impracticable y realizable (si no se cuenta con la ayuda de un ordenador, muy probablemente, cuántico), ha mantenido “en jaque” a muchos matemáticos durante 18 años. Es, de hecho, uno de los problemas del milenio en el área de las matemáticas. Dichos problemas fueron seleccionados por la Clay Mathematics Institute, y anunciados en el Collège de France en el año 2000. La resolución de éstos conlleva a un premio de un millón de dólares. Aquí les dejo un link que los enviará a un archivo en pdf donde se explican estos 7 problemas del milenio y, a su vez, explica otros problemas de años anteriores que pudieron ser resueltos gracias al ingenio (trabajo duro y años de estudio) del ser humano.

El problema de las mil reinas se refiere al problema “P=NP” de los 7 antes presentados. Éste presenta lo siguiente: De acuerdo a la teoría de la complejidad se debe de encontrar una relación entre clases de complejidad P y NP.

Dicho en otras palabras: la teoría de la complejidad se basa en los procedimientos computacionales, es decir, cuánto tarda un computador en ordenar, por ejemplo, una serie de números a través de algoritmos (los algoritmos son procesos, tal como el levantarse, lavarse los dientes, bañarse; incluso en eso se usa un algoritmo, ya que es un proceso). En dicha teoría llamamos NP al conjunto de problemas que podemos comprobar si una respuesta al problema es correcta o no en un tiempo razonable (polinomial), y P al conjunto de problemas en los que podemos encontrar una respuesta en un tiempo razonable. Lo difícil de todo esto es saber si un problema que esté en NP estará también en P; el que podamos comprobar fácilmente un problema no implica que podamos encontrar fácilmente una solución.

Esto nos lleva al problema de las reinas en ajedrez, el cual, si se lograse solucionar, significaría que quien lo resuelva podrá ganar un millón de dólares, ya que la resolución de dicho problema dará también con la de “P versus NP” o “P=NP”.

El problema de las mil reinas es el siguiente:

  • En un tablero normal (donde se cuentan con casillas negras y blancas proporcionalmente la una de la otra) sólo se tienen piezas de la dama.
  • Se cuenta con un total de 1000 damas.
  • El tablero en vez de ser de 8×8 (como cualquier otro), constará de 1000 columnas por 1000 filas.
  • Las damas deberán de estar colocadas de tal forma que una no atacará a las otras, y algunas de estas reinas ya están colocadas en el tablero, por lo que no se podrán mover.
  • El algoritmo que resuelva dicho problema debe ser polinomial.

Lo que se nos presenta aquí es como el problema, ya resuelto, de lo que fue el problema de las 8 damas, en un tablero de 8×8, sólo que este de las 100 reinas tiene mayor magnitud. En el problema de las 8 damas se llegó a encontrar 92 formas de resolverlo. En el de 1000 reinas, aún es un misterio.

Esta es una noticia que lleva circulando alrededor de 18 años, y en ese transcurso, de los 7 problemas del milenio, sólo se ha podido resolver uno, el cual fue la Conjetura Poincaré.

Muchos de nosotros, cuando aún andábamos en primaria, secundaria o preparatoria, siempre sentenciábamos a las matemáticas de aburridas, sin sentido (“jamás ocuparé esto en la vida”) e incluso aterradoras, pero quién iba a decir que algún día las misma nos servirían para poder ganar un millón de dólares.

En realidad, las matemáticas tienen más importancia en nuestra vida y la ciencia que las que uno pueda creer. He de admitir que incluso yo, quien llegó a criticar las matemáticas, he podido encontrar la belleza en ellas, a tal grado de decir: “Amo las matemáticas”. De hecho, un estudio llevado a cabo en la University College London demostró que, al presentarles a un conjunto de matemáticos ecuaciones “bellas” y otras “feas”, partes del cerebro (las mismas que se activan cuando apreciamos una obra de arte; pinturas, música, esculturas, etc.) se activaban al momento que se mostraba la serie de ecuaciones.

En otro estudio hecho por el Journal Frontiers in Human Neuroscience, uno de los investigadores, el profesor Semir Zeki declaró: “Un gran número de áreas del cerebro están envueltas al ver ecuaciones; pero cuando alguien mira a una fórmula calificada como ‘bella’ se activa el cerebro emocional (el córtex medio orbito frontal) como cuando vemos un cuadro o escuchamos una pieza musical”.

Las matemáticas son increíbles y aprendes tanto de ellas que logras entender de una manera más profunda y curiosa a la naturaleza, e incluso la naturaleza del hombre. No por nada muchas otras áreas del conocimiento utilizan esta disciplina.

Si te interesa meterte a este mundo de las matemáticas, y no sólo de esta área sino de la ciencia en general, te invito a que leas “Alex en el País de los Números” de Alex Bellos. Será un viaje en el que no encontrarás vuelta atrás, ya que te sumergirás en un mundo hasta hoy desconocido, y a lo mejor, puedas resolver el problema de las 1000 reinas mejor que un computador cuántico.


Fuentes de referencia: .http://ciencias.udea.edu.co/documentos/jueves/MilleniumPrizeA.pdf


Imagen: https://www.neoteo.com/el-problema-de-las-1000-reinas-gana-un-millon-de-dolares-resolviendo-el-problema-con-un-algoritmo/

Comentarios

Comentarios

Jóvenes Construyendo

Jóvenes Construyendo es una plataforma en línea que ofrece un espacio de expresión para jóvenes con grandes ideas con el objetivo de compartir puntos de vista y propuestas sobre juventud.