NeoFronteras

Encuentran una aproximación al número de maneras que hay de colocar n reinas sin que ninguna se amenace en un tablero n por n casillas.

¿Es todo computable en un tiempo razonable? No es fácil contestar a esta pregunta, pero la pregunta es tan interesante que contestar al problema del milenio relacionado con este tema está premiada con un millón de dólares. Dicho problema es demostrar o refutar que P sea igual a NP. Para poder entender bien todo esto nos tendremos que adentrarnos en el mundo de la complejidad computacional.

Lo primero es pensar en que un algoritmo no es más que una serie de cálculos que nos permiten, a partir de una entrada, obtener una salida que es la solución al problema planteado en la entrada. Así, la entrada puede ser dos números y salida la suma de los dos. Además, para obtener la salida se necesita un tiempo que será más pequeño en función de lo eficiente que sea el algoritmo.

Aquí tenemos que distinguir entre la complejidad algorítmica respecto al tiempo y la complejidad algorítmica respecto al espacio. Este último caso se refiere a la memoria que se necesitaría para llevar hasta el final el algoritmo y obtener la salida. Un ejemplo de esto sería el de dimensionar una matriz muy grande para así calcular su determinante. El primer caso de la complejidad temporal es el que trataremos aquí y es el tiempo que tardaría el algoritmo en hacer el cálculo y que dependerá del tamaño de la entrada y del número de operaciones elementales que serían necesarias para obtener la salida.

La entrada y cálculo puede ser algo más complejo que dos números y sumarlos. Así, por ejemplo, podría ser la resolución de un sistema de ecuaciones, el cálculo de un determinante o la resolución de un sudoku.

Cuánto tiempo tarde el algoritmo en resolver el problema dependerá del tamaño de la entrada. Así, no es lo mismo resolver un sistema de 3 ecuaciones que un sistema de 1000 ecuaciones. El tiempo dependerá tanto del tamaño del problema, al que llamaremos n, como del algoritmo en sí mismo y su eficacia a la hora de tener un número reducido de operaciones. Así, una pregunta legítima en este caso es preguntarse cuánto tiempo se tarda en calcular el determinante de una matriz n×n.

Se sabe que hay problemas que tienen una complejidad polinómica. Es decir, que el tiempo necesario para que un algoritmo lo resuelva dependerá de un polinomio en n. Así, la suma de dos números tiene una complejidad de O(n), que se lee «del orden de n», lo que significa que el tiempo de cálculo crece como un polinomio de grado 1. La multiplicación tiene una complejidad de O(n²) y la resolución de un sistema de ecuaciones lineales por Gauss de O(n³), es decir, que tienen una complejidad que va con un polinomio de grado 2 y 3 respectivamente. Todos los problemas que son resolubles con algoritmos de complejidad polinómica se agrupan en un conjunto o clase al que llamaremos P.

Naturalmente los algoritmos se pueden mejorar y podríamos encontrarnos con la sorpresa de que alguien halle un algoritmo que resuelva un problema en un tiempo que dependa de una polinomio de menor grado, pero esto no es necesariamente posible. Además, no todos los problemas se pueden resolver en tiempo polinómico.

Así, hay algoritmos cuya complejidad es exponencial, es decir que van con O(aⁿ), y cuyo tiempo de ejecución crece muy rápidamente a partir de cierto n. Por tanto, necesitan de mucho más tiempo que los algoritmos polinómicos. Un ejemplo de esto es el del sudoku generalizado para un tamaño n (se puede usar letras además de números en las casillas). Todos los algoritmos conocidos para resolver el sudoku generalizado son exponenciales. Lo que sí hay es un algoritmo polinómico para comprobar que una solución dada al sudoku generalizado es correcta, pues sólo tenemos que sumar filas y columnas.

La clase NP está compuesta por aquellos problemas de complejidad exponencial cuya comprobación es polinómica, como el problema del sudoku generalizado. La clase P anterior se considera un subconjunto de NP. La pregunta del milenio es si P=NP, algo que no sabemos todavía. Puede que para ciertos problemas haya algoritmos polinómicos que todavía no hemos encontrado y para los que solo tenemos ahora algoritmos exponenciales. O puede que alguien demuestre que no existen y que por tanto algunos problemas situados en NP nunca estén en P y que, por tanto, P no sea igual NP. Esto último sería más fácil de demostrar porque afirmar que N=NP implicaría que todos los elementos de NP (incluso los no planteados aún) están en P. En cualquier caso, la demostración positiva o negativa a que NP sea igual P está premiada con ese millón de dólares del Instituto Clay de Matemáticas.

Una manera de atacar este enigma es considerar otra clase: el conjunto NP-completo, que es subconjunto de NP. Los problemas de NP-completos están conectados con todos los demás de NP de tal forma que esos problemas de NP se pueden reducir a problemas de NP-completos de forma polinómica. Es decir, si pudiésemos resolver un problema NP-completo con un algoritmo polinómico entonces, como están conectados polinómicamente con todos los demás de NP, estos también podrían resolverse en tiempo polinómico. O lo que es lo mismo, si tuviéramos un algoritmo que resolviera un problema NP-completo de forma polinómica (rápido) entonces se podría usar para resolver otros problemas de NP de forma también rápida. Por tanto, si somos capaces de resolver un problema NP-completo de forma polinómica entonces esto implicaría que NP=P. Aunque el demostrar algo así no implica que encontremos los algoritmos adecuados de la noche a la mañana. Todavía no se ha demostrado que exista un solo problema de NP-completo resoluble polinómicamente.

El sudoko generalizado es un problema NP-completo, pero también se sabe de otros. Uno de ellos es el colocar reinas o damas en un tablero de ajedrez sin que se amenacen. El problema algorítmico aquí planeteado es precisamente el de colocar esas reinas. Aunque el problema combinatorio consiste en saber de cuántas maneras se pueden colocar para que ninguna ataque al otra.

La versión original del problema matemático de combinatoria con 8 reinas apareció por primera vez en una revista alemana de ajedrez en 1848 como el problema de las ocho reinas y la respuesta correcta sobre cuántas maneras hay de hacerlo surgió un par de años después. Resulta que hay 92 maneras, pero solamente 12 son distintas.

Este problema lo podemos generalizar al caso de n reinas a colocar en un tablero n×n. No se conocen algoritmos polinómicos que resuelvan el problema de reinas generalizado, pero si que se puede comprobar soluciones polinómicamente. Es decir, este problema está en NP. Además, es también NP-completo, por lo que es un problema interesante. Cualquier avance en este problema de la reinas es por tanto importante. Todo este preámbulo nos ha servido para entender la importancia de un resultado reciente.

Ahora se ha calculado cuántas formas hay de colocar n reinas en este problema generalizado de las reinas en un tablero n×n. Esta versión más amplia del problema de n-reinas surgió en 1869 y el problema combinatorio asociado a él para cualquier n permaneció sin respuesta hasta la actualidad.

Naturalmente durante este tiempo se han calculado esto para distintos valores. Así, por ejemplo, para n=25 hay 275 986 683 743 434 configuraciones distintas y 2 207 893 435 808 352 configuraciones en total.

Michael Simkin, postdoc en la Universidad de Harvard, ha calculado ahora que hay alrededor de (0.143n)ⁿ formas totales de colocar n reinas sin que ninguna se amenace entre sí en un tablero n×n.

La ecuación final de Simkin no proporciona la respuesta exacta, sino que simplemente dice que esta cifra es lo más cercana al número real que se puede obtener en este momento.

Como podemos apreciar, no es una solución al problema de complejidad algorítmica, sino una solución aproximada al problema combinatorio asociado al problema las n-reinas.

En este caso, para, por ejemplo, un tablero de ajedrez extremadamente grande con un millón de casillas de lado se tiene que multiplicar 0,143 por un millón, lo que daría como resultado unas 143 000. Luego, ese número se elevaría a la potencia de un millón, lo que significa que se multiplica por sí mismo un millón de veces. La respuesta final es un número con cinco millones de dígitos.

Simkin pudo llegar a esta ecuación al comprender el patrón subyacente de cómo se tendría que distribuir un gran número de reinas en estos enormes tableros de ajedrez, ya sea que se concentraran en el medio o en los bordes, y luego aplicó técnicas y algoritmos matemáticos conocidos.

«Si me dijera que quiero que ponga sus reinas de tal y tal manera en el tablero, entonces podría analizar el algoritmo y decirle cuántas soluciones hay que cumplen con esta restricción. En términos formales, reduce el problema a un problema de optimización», dice Simkin.

Al centrarse en los espacios que tienen mayores posibilidades de ser ocupados, Simkin calculó cuántas reinas habría en cada sección del tablero e ideó una fórmula para obtener un número válido de configuraciones. Los cálculos dieron como resultado lo que se conoce como el límite inferior: el número mínimo de configuraciones posibles.

Una vez que tuvo ese número, Simkin usó una estrategia conocida como el método de la entropía para encontrar el límite superior, que es el mayor número de configuraciones posibles.

Simkin encontró que la respuesta del límite inferior coincide casi perfectamente con la respuesta del límite superior. En pocas palabras, mostró que la respuesta exacta se encuentra en algún lugar entre los dos límites en un espacio matemático relativamente pequeño.

Trabajar en el problema ha sido una prueba de paciencia. Hace cuatro años, como estudiante de doctorado de la Universidad Hebrea de Jerusalén, visitó al matemático y genio del ajedrez Zur Luria en el Instituto Federal Suizo de Tecnología en Zúrich. La pareja colaboró y desarrolló nuevas técnicas para llegar a una respuesta. Al final, después de dos años de trabajo, solo encontraron una mejor cifra de límite inferior y supieron que les faltaba algo.

Simkin terminó su doctorado en 2020 y se mudó a Boston para comenzar a trabajar en Harvard. El problema siempre estuvo en su mente y volvió a él cuando se dio cuenta de que tenía que empezar a centrarse en los espacios donde estarían las reinas en lugar de darle el mismo peso a cada espacio.

Aunque teóricamente es posible acercarse un poco más a una respuesta todavía más exacta, Simkin por ahora es feliz de dejar que alguien más lo haga.

«Creo que personalmente puedo terminar con el problema de las n-reinas por un tiempo, no porque no haya nada más que hacer, sino porque he estado hasta soñando con el ajedrez y estoy listo para seguir adelante con mi vida», dijo.

Copyleft: atribuir con enlace a https://neofronteras.com

Fuentes y referencias:
Preprint en ArXiv.
Animación: Wikipedia