Un artículo reciente sobre la complejidad del n- Queens Completion Problem de investigadores de la Universidad de St Andrews puede señalar el camino hacia un nuevo ataque contra uno de los problemas del Premio del Milenio, el problema P vs NP . El documento es una contribución interesante a la teoría de la complejidad, pero no dice que la búsqueda de una solución correcta al enigma de 8 Queens o incluso a la n -Queens puzzle para toda n justificaría la concesión del Premio del Milenio.
Como comenta Ian Gent, uno de los autores: "El acertijo 8-Queens en el tablero de ajedrez es un rompecabezas clásico, y todas sus soluciones se conocen desde hace mucho tiempo. Se sabe también que el más general n -Queens rompecabezas puede ser resuelto en todos los tableros de ajedrez tamaño mayor: que es el rompecabezas de la colocación de n reinas en una n- subproductos n tablero de ajedrez de modo que no reina está atacando otro.
La nueva investigación se refiere al problema de finalización n-Queens , donde no solo el tablero es más grande, sino que también se han colocado algunas reinas. Es decir, si algunas reinas ya se han colocado en el n- subproducto n bordo, se puede encontrar una solución a la n-Queens rompecabezas sin mover ninguna de esas reinas? La contribución técnica que se afirma en este documento es que el n -Problema de finalización de Queens cae en la clase conocida como NP-Complete . Si es correcto, esto significa que cualquier algoritmo que pueda resolver el n -Problema de terminación de Queens puede usarse indirectamente para resolver cualquier otro problema en la clase NP. Esto no se aplica al rompecabezas n -Queens original , porque la adición de reinas pre-ubicadas es crítica.
"Desafortunadamente, algunos informes de nuestro trabajo han dado la impresión de que resolver el rompecabezas de 8 reinas, o el rompecabezas de n -queens para todos los n , podría resultar en la concesión del Premio del Milenio. Este no es el caso, por dos razones. En primer lugar, como se acaba de mencionar, el documento trata sobre el problema n -Queens Completion, no el rompecabezas n -Queens original . En segundo lugar, incluso el descubrimiento de una solución algorítmica para el rompecabezas n -Queens Completion para todos n no sería suficiente. sería necesario sería una prueba de que hay un algoritmo que puede resolver el rompecabezas n -Queens Completion en tiempo polinomial, o una prueba de que no existe tal algoritmo ".
Agradecimientos a que encontró el enlace que acabo de traducir
Como comenta Ian Gent, uno de los autores: "El acertijo 8-Queens en el tablero de ajedrez es un rompecabezas clásico, y todas sus soluciones se conocen desde hace mucho tiempo. Se sabe también que el más general n -Queens rompecabezas puede ser resuelto en todos los tableros de ajedrez tamaño mayor: que es el rompecabezas de la colocación de n reinas en una n- subproductos n tablero de ajedrez de modo que no reina está atacando otro.
La nueva investigación se refiere al problema de finalización n-Queens , donde no solo el tablero es más grande, sino que también se han colocado algunas reinas. Es decir, si algunas reinas ya se han colocado en el n- subproducto n bordo, se puede encontrar una solución a la n-Queens rompecabezas sin mover ninguna de esas reinas? La contribución técnica que se afirma en este documento es que el n -Problema de finalización de Queens cae en la clase conocida como NP-Complete . Si es correcto, esto significa que cualquier algoritmo que pueda resolver el n -Problema de terminación de Queens puede usarse indirectamente para resolver cualquier otro problema en la clase NP. Esto no se aplica al rompecabezas n -Queens original , porque la adición de reinas pre-ubicadas es crítica.
"Desafortunadamente, algunos informes de nuestro trabajo han dado la impresión de que resolver el rompecabezas de 8 reinas, o el rompecabezas de n -queens para todos los n , podría resultar en la concesión del Premio del Milenio. Este no es el caso, por dos razones. En primer lugar, como se acaba de mencionar, el documento trata sobre el problema n -Queens Completion, no el rompecabezas n -Queens original . En segundo lugar, incluso el descubrimiento de una solución algorítmica para el rompecabezas n -Queens Completion para todos n no sería suficiente. sería necesario sería una prueba de que hay un algoritmo que puede resolver el rompecabezas n -Queens Completion en tiempo polinomial, o una prueba de que no existe tal algoritmo ".
Agradecimientos a que encontró el enlace que acabo de traducir