El vigués Clemente García Estévez asegura haber resuelto el "problema de las mil reinas", para cuya resolución se ha llegado a ofrecer un premio de un millón de dólares.
El problema de las mil reinas es una extensión del pasatiempo de las ocho reinas, propuesto por el ajedrecista Alemán Max Bezzel en 1848. Consiste en colocar sobre un tablero de ajedrez ocho reinas sin que se amenacen entre ellas, es decir, que no se encuentren en su misma fila, columna o diagonal. Años después, el matemático alemán Franz Nauck publicó las primeras soluciones en un periódico de su país y extendió el puzle a "n" reinas en un tablero de "n" cuadrados.
El problema, relativamente sencillo para 8 reinas, se hace mucho más complejo cuantas más reinas (y cuadrados en el tablero) se incluyan, ha intrigado a matemáticos tan célebres como el germano Carl Fiedrich Gauss, que da nombre a la famosa gráfica conocida como campana de Gauss, muy utilizada para describir la evolución de esta pandemia de coronavirus.
El de las mil reinas es más que un pasatiempo de ajedrez. En realidad, encierra una de las preguntas sin resolver más importantes de la ciencia computacional. En 2017, los científicos Ian Gent y Peter Nightingale, de la Universidad de St Andrews, en Escocia, retaron a los programadores a resolver este problema para valores muy grandes de "n", ofreciendo un premio de un millón de dólares a quien lo lograra. Estos científicos británicos señalaron que un ordenador puede resolver el problema de las 8 reinas en micro segundos, pero cuando el tablero se ampliaba a 100x100 o 1.000x1.000 cuadrados, los programas informáticos no podían manejar esos números tan grandes en un periodo razonable de tiempo: en teoría cualquier "software" tardaría mil años en resolverlo.
"P versus NP"
Los matemáticos e informáticos consideran el de las mil reinas como un problema "P versus NP". En ciencia computacional, el "P versus NP" es un problema irresuelto que se pregunta si cada problema que puede ser rápidamente verificado puede ser también fácilmente resuelto.
Se entiende mejor con un ejemplo. Pongamos que tenemos que organizar el banquete de nuestra boda y que tenemos una lista de 400 amigos y familiares como potenciales invitados. Sin embargo, nuestro presupuesto es limitado y debemos acotar la lista de invitados a 100 y distribuirlos en 10 mesas de 10 comensales cada una. Para complicar más las cosas, la suegra nos da una lista de esos amigos y familiares que se llevan mal entre sí y que por tanto no deben compartir mesa. La suegra podrá verificar rápidamente si hemos resuelto el problema, es decir, si hemos colocado los comensales sin que coincidan en una mesa dos o más que se lleven mal; sin embargo, la tarea de generar esa distribución desde cero es muchísimo más difícil. El número de maneras para elegir cien invitados de la lista de 400 sería mayor que el número de átomos del universo conocido. Los informáticos creen que ningún ordenador será capaz de resolver el problema por "fuerza computacional bruta", es decir, comprobando cada combinación posible de 100 invitados.
El problema "P versus NP" o simplemente "problema NP" fue formulado independientemente por dos científicos computacionales, el estadounidense Stephen Cook y el ucraniano Leonid Levin en 1971, y es tan relevante que el Clay Mathematics Institute de Massachusetts, Estados Unidos lo considera uno de los Problemas de Premio del Milenio para los que ofrece una recompensa de un millón de dólares para quien ofrezca la primera solución correcta.
En teoría, según Gent y Nightingale, un algoritmo que sirva para resolver el problema de las mil reinas servirá también para solventar cualquier problema NP, "algunos triviales, como realizar el grupo más grande de Amigos de Facebook que no se conocen entre sí, y otros muy importantes, como descifrar los códigos que mantienen seguras todas nuestras transacciones en internet". No pocos científicos creen que esto es imposible, de ahí lo fascinante del desafío matemático que el vigués Clemente García Estévez asegura haber resuelto, como explica en este artículo en FARO DE VIGO.
