Investigadores de la Universidad de St. Andrews ofrecen una recompensa de un millón de dólares para quien pueda desarrollar un algoritmo que supere al viejo acertijo del ajedrez conocido como “el problema de las ocho reinas”.
|
etiquetas: 1000 reinas , problema , ajedrez , recompensa , pnp
1.- lo necesitan para resolver un problema que tienen.
2.- quieren saber si alguien es capaz de resolverlo porque les reventaría algún sistema criptográfico o similar.
Hay problemas que (ahora mismo) no se pueden resolver en un tiempo polinomial, es decir, que siendo n los datos de entrada se tarda por ejemplo 2n segundos en resolverlo. Pero la comprobación del resultado tiene un coste polinómico, por ejemplo n segundos en realizar la comprobación.
La pregunta que subyace es si los algoritmos no polinómicos que se pueden comprobar de forma polinómica podrían mejorarse para que fueran polinómicos, es decir que si el conjunto P es igual al NP. Normalmente se asume que esto es falso, pero nadie lo ha demostrado.
Si se demuestra que P = NP, significaría que los problemas que ahora se suponen no polinómicos (porque el mejor algoritmo que los resuelve es no polinómico, como el de las 1000 reinas) son realmente polinómicos. Es decir, tiene que existir un algoritmo polinómico que los resuelve aunque nadie lo haya descubierto.
Ahora mismo nadie sabe si hay una solución mejor para el algoritmo de las 1000 reinas, si la encuentras acabas de transformar un algoritmo NP a P, por lo que probablemente puedas demostrar que P = NP.
en.wikipedia.org/wiki/Eight_queens_puzzle
Imagino que esto se referira a una solucion generalizada (NxN), o 8x8 con alguna condicion en especial... Pero tal como lo explica la entradilla, ya esta resuelto. Esto me parece clickbait.
Edito: El titular dice una cosa, la entradilla otra.
De todad formas lo que esta gente pregunta tiene poco que ver con el ajedrez.
#10 De hecho el premio no es por conseguir una solución (eso es facilísimo). El premio es por diseñar un algoritmo generalizable para NxN que demuestre que funciona siendo aplicado a 1000 x 1000.... entre otras.
Ahora.... Va a tardar.
<ironic>
Saludos a mi profesor, Oliverio... que majete era... siempre con una sonrisa en la cara...
</ironic>
Creo que solo buscaban suspender al mayor número de alumnos.
Lo que piden es un algoritmo mejor, no necesariamente uno polinomial.
Ahora mismo nadie sabe si hay una solución mejor para el algoritmo de las 1000 reinas, si la encuentras acabas de transformar un algoritmo NP a P, por lo que probablemente puedas demostrar que P = NP.
Si consigues un algoritmo polinomial para cualquier problema NP-completo (y el de las reinas lo es) ya has demostrado que P = NP porque no es complicado transformar cualquier otro problema NP al ya resuelto y sobre esto ya está el trabajo hecho.
Sencillamente, el problema planteado de las 1000 reinas es parecido a lo que en matemáticas llaman complegidad P vs NP, que se producen cálculos tan elevados que ni la tecnología actual no es capaz de hacerlos, por lo que encontrar un sistema o algoritmo que facilitase esos cálculos sería revolucionario.
La confuión viene, a que el Problema de P vs NP en el mundo matemático es considerado como uno de los Problema del Milenio que SI están premiados desde el año 2000 por su complegidad, pero este de las mil reinas aunque sea parecido no.
fuente: es.wikipedia.org/wiki/Problemas_del_milenio
Mira: www.st-andrews.ac.uk/news/archive/2017/title,1539813,en.php
Es el "Clay Mathematics Institute in America" quien ofrece 1 millón de dólares de recompensa (no el Sant Andrews), que es una institución/fundación matemática fundada en la Universidad de Cambridge y ofrece premios e incentivos para matemáticos. Y no está el de las 1000 damas entre ellos.
El premio es, como he escrito antes, por refutar o encontrar un algoritmo que de una solución rápida del problema de P vs PN, no por resolver el problema de las mil damas. Que como dice el artículo que tu mismo has puesto, el algoritmo de la solución rápida al problema de las mil damas acercaría mucho al premio, o lo que es lo mismo, al premio por la solución del problema de P vs PN.
Que de verdad ccguy, si quieres hacer un zasca o parecido, por lo menos haz el favor de documentarte bien.
«Visit the Clay Institute website for more information on the US$1m prize.»
El enlace:
www.claymath.org/millennium-problems/p-vs-np-problem
Y por si queda alguna duda, en esta otra noticia, el profesor Nightingale (de la noticia que enlazas) aclara el asunto:
«Nobody knows, even very roughly, how hard NP-complete problems are. They could be as easy as sorting a list of names into alphabetical order, or they could be exponentially harder. Finding out which they are is called the P vs NP problem, and it is one of the great unsolved mathematical problems – so much so that the Clay Mathematics Institute (not me) is offering a prize of US$1m for the solution of P vs NP.»
theconversation.com/why-the-worlds-toughest-maths-problems-are-much-ha
P.D.: Tampoco hace falta que os peleéis. La noticia en concreto es efectivamente sensacionalista/errónea, pero el asunto no deja de ser interesante y curioso.
cc #32
elpais.com/elpais/2017/09/04/ciencia/1504535610_082169.html
El reto consiste en colocar 1.000 reinas en un tablero de 1.000x1.000 sin que se coman unas a otras. Es decir, que no haya dos reinas en la misma fila, columna y diagonal. Varios científicos llevan años intentando crear el algoritmo que encuentre todas las soluciones del enigma.
No creo que encontrar una única solución sea excesivamente complicado hasta el punto que no se conozca ninguna o que sea "eterno" encontrarla, el problema es encontrarlas todas, eso sí es una putada.
PS: Y por lo que veo, según #36 en la página que cita el país no se refiere a ese problema en particular, así que además sería errónea.
Simplificándolo al máximo, tendrías que programar un algoritmo de fuerza bruta que encuentre todas las soluciones y tirar a la basura la complejidad para simplificar el algoritmo que tendrías que escribir. Ni al guardar ni al generar las soluciones tienes que tener toda la matriz, solo te basta con tener la altura por columnas a la que está cada reina por ejemplo (3, 1, 6, 2, 8, 6, 4, 7). Al guardar las soluciones simétricas lo que podrías hacer es que al obtener una solución, generar sus 4 simetrías (entiendo que solo había que descontar rotaciones), y guardas la que tenga una cardinalidad menor, para luego guardarla en un mapa. Por ejemplo, si de las soluciones equivalentes tienes (3,1,6...), (4,5,9...) y (1,8,3...) solo guardas o compruebas la solución que empieza por 183.
Todo eso me parece excesivo para un examen. Quizás es mal profesor o como dice otro comentario tenía algún truco que no pillasteis, esos son los exámenes para ir a revisión y solicitar que el profesor muestre la solución y que justifique que el examen se puede hacer en el tiempo previsto.
En aquella época estaban cambiando los planes de estudios a cuatrimestrales. Por cosas de la vida me cambié de universidad y me pilló el lío el cambio de planes . Mientras esperaba que me convalidaran las asignaturas y por que me salia mas barato el curso completo decidí no tener que esperar y me examiné en la nueva universidad. En todo el año en programación 1 y programación 2 (estas cuatrimestrales) no daban el 50% de lo que yo había dado en la anual. Un claro ejemplo era la creación y acceso a ficheros (secuencial, aleatorio, etc.) que en la nueva universidad ni se daban en toda la carrera.
Como curiosidad por aquella época estaba empezando el auge de la programación orientada a objetos y no se daba. Tampoco acceso a las BB.DD. Vamos, que creo que había más temario por un lado y menos por otro.
Tuve un profesor de C, que la licenciatura que tenia era de Química.
Si en un examen con 100 alumnos, solo uno consigue un 80% de la nota. ¿Tu crees que el problema de que los alumnos no estudian o de que los profesores no saben explicar (o directamente van a suspender para que el proximo año te tengas que volver a matricular)?