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”.
#7:
#6 Realmente este es un problema concreto del problema ¿P = NP?, que es por lo que te dan un millón de leuros.
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.
#4:
#2 Si claro. La última partida que tuve con una niña de 5 años, me llegó a coronar todos los peones, el osito, la figura del roscón y perdí la partida porque el perro se llevó mi rey.
Cuando se da un premio de este tipo suele ser por uno de estos motivos.
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.
#6 Realmente este es un problema concreto del problema ¿P = NP?, que es por lo que te dan un millón de leuros.
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.
#7Realmente este es un problema concreto del problema ¿P = NP?, que es por lo que te dan un millón de leuros.
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.
Erróneo porque la Universidad de St. Andrews no ofrece ninguna recompensa. Unos investigadores de la universidad han demostrado que el problema de las reinas es "NP hard". Nada mas. Si alguien es capaz de resolver el problema de N reinas (no 1000!) en tiempo polinomial, entonces puede ganar el premio Millennium de un millón de collares, como bien explica el #7.
#23 No solo a una tutoría sino además a las revisiones. Yo siempre iba aunque no fuera porque me hiciera falta subir nota, iba para saber en qué me había equivocado, o para saber como corregía ese profesor los exámenes. Muchas veces te das cuenta de que el profesor se equivoca al corregir, y en algunas ocasiones incluso que las soluciones que ellos proponían no eran válidas, en una de ellas porque el ejercicio directamente no tenía solución con las restricciones del examen. Así que no le quedó más remedio que aceptar el medio párrafo que le escribí durante el examen justificando una solución de dos líneas.
#2 Si claro. La última partida que tuve con una niña de 5 años, me llegó a coronar todos los peones, el osito, la figura del roscón y perdí la partida porque el perro se llevó mi rey.
#9 Me surge la duda de tener en cuenta que el rey contrario no puede estar en jaque y llegará un momento con X reinas que sea casi imposible que no lo esté y eso teniendo en cuenta que las otras piezas no hayan caído.
#11 No necesariamente... el rey rival puede (o más bien debe) estar parapetado detrás de sus piezas.
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.
Esto me recuerda a un pedazo problema que nos puso el profesor de fundamentos de la programación en la facultad en primero. Era el problema de las ocho reinas devolviendo el número de soluciones, pero en un tablero NxM (no hay problema hasta aquí, backtraking a tope y listo, además era parte de la asignatura) pero con la condición de que si M=N había que eliminar todas las soluciones simétricas (giradas en todos los planos), Vamos, que o se te aparecía la musa para encontrar algún algoritmo para eliminarlas o a guardar cada solución e ir girando la matriz (teniendo que usar otra mas temporal para comprobar), ademas de tener que ir creando una cola de matrices para tener que guardar cada solución nueva encontrada y compararla con las siguientes. Nada mal para un problema que valía 3 puntos en un examen de 2 horas. Se le fue un poco la pinza
#16 Era un gran profesor. Explicaba muy bien y ya avisaba que en sus exámenes siempre había una parte dependiente de que, como decía él, "se te apareciese la virgen". Decía que la programación y la algoritmia era saber usar y enteder una serie de métodos para resolver un problema y si era necesario inventar un nuevo método (de ahí lo de eliminar las simétricas). El resto del examen era bastante normalillo, pero si querías nota tenias que demostrar que sabías usar la cabeza para resolver un nuevo problema, más allá de lo explicado. A mi personalmente ese modo de pensar me pareció cojonudo, pero te puedo asegurar que muchos alumnos protestaron y le preguntaron que como se hacía eso, a lo que respondió "Aun me lo tengo que pensar". Un crack
#39 Parte está respondido en #30. La cursé en el año 92-93. Era anual y se complementaba con un laboratorio de programación (el primer cuatrimestre QuickBasic y el segundo Pascal). La verdad es que daban caña.
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.
#13 Puff me has recordado lo que me costó a mi aprobar la asignatura de Algoritmos y Estructuras de Datos, era con diferencia la más chunga de la carrera, al menos en la EUITIO de Oviedo donde yo estudié. La aprobé la última, por poco, y después de dedicarme un año entero sólo a ella. Eso fué en 2002, me hago viejuno...
Saludos a mi profesor, Oliverio... que majete era... siempre con una sonrisa en la cara...
#13 Yo recuerdo un examen en Diciembre de programación. De todos los que nos presentabamos, solo uno saco un 80% de la nota, dos sacaron un 40% y varios entre ello yo, un 20%. El problema valio 3 ó 4 puntos y aunque me pase una hora dandole vueltas, nada. Y luego lo repitieron en el examen de febrero de Algoritmos y Estructuras de Datos.
Creo que solo buscaban suspender al mayor número de alumnos.
#23 Algunos profesores solo sabian soltar su rollo y comparar el examen con la solución que otro profesor habia propuesto...
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)?
#13 ¿En qué año la cursaste? A mi me parece algo totalmente exagerado, y seguramente propio de un mal profesor, y no creo que se pueda hacer en un tiempo razonable teniendo en cuenta que tendrías los 7 puntos del resto del examen en juego ( y que requieran su tiempo). También es un problema en el que es muy fácil confundirse con los índices y dudo que en primero sea razonable exigir backtracking, aunque depende de la intensidad horaria o d si la asignatura era anual.
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.
La noticia es falsa y sensacionalista. Ni la Universidad de Sant Andrews ofrece recompensa, ni hay recompensa de un millón por la solución de este juego.
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.
#33 Se nota que no te has leido el link que has puesto, porque reafirma lo que he dicho.
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.
#33 Como ya te han comentado, al resolver ese problema de convertir un problema NP en P, se estaría resolviendo uno de los problemas del milenio. No es que se busque una solución al problema de las n reinas en concreto. En esa propia noticia que pones, cuando hablan del premio, enlazan al problema del milenio P vs NP:
«Visit the Clay Institute website for more information on the US$1m prize.»
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.» https://theconversation.com/why-the-worlds-toughest-maths-problems-are-much-harder-than-a-chess-puzzle-and-well-worth-us-1m-83516
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.
No he terminado de ver todo el vídeo porque se dedica principalmente a explicar el problema, y parece que no mucho a hablar del titular. Quizás se refiera a resolver el problema de P=NP o quizás se refiera a esta otra noticia:
https://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.
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.
Comentarios
Creo que el de Derivando ha sido víctima de la confusión de otros, según este otro artículo https://theconversation.com/why-the-worlds-toughest-maths-problems-are-much-harder-than-a-chess-puzzle-and-well-worth-us-1m-83516
Cuando se da un premio de este tipo suele ser por uno de estos motivos.
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.
#6 Realmente este es un problema concreto del problema ¿P = NP?, que es por lo que te dan un millón de leuros.
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.
#7 ah... los problemas del milenio (http://www.claymath.org/millennium-problems).
#7 Realmente este es un problema concreto del problema ¿P = NP?, que es por lo que te dan un millón de leuros.
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.
Erróneo porque la Universidad de St. Andrews no ofrece ninguna recompensa. Unos investigadores de la universidad han demostrado que el problema de las reinas es "NP hard". Nada mas. Si alguien es capaz de resolver el problema de N reinas (no 1000!) en tiempo polinomial, entonces puede ganar el premio Millennium de un millón de collares, como bien explica el #7.
#31 https://www.st-andrews.ac.uk/news/archive/2017/title,1539813,en.php
Si no hubiera discriminación positiva se movería una puta casilla y ya estaría resuelto.
#1 Uhmmmm, usando pensamiento lateral eh?, se puede?
#23 No solo a una tutoría sino además a las revisiones. Yo siempre iba aunque no fuera porque me hiciera falta subir nota, iba para saber en qué me había equivocado, o para saber como corregía ese profesor los exámenes. Muchas veces te das cuenta de que el profesor se equivoca al corregir, y en algunas ocasiones incluso que las soluciones que ellos proponían no eran válidas, en una de ellas porque el ejercicio directamente no tenía solución con las restricciones del examen. Así que no le quedó más remedio que aceptar el medio párrafo que le escribí durante el examen justificando una solución de dos líneas.
#11 Con 9 reinas colocadas en las 9 casillas de una esquina ya no hacen jaque a mucha zona del tablero.
¿Puede una partida normal de ajedrez llegar a 8 reinas (la original y 7 peones promocionados)?
#2 No creo que sea posible que tantos peones puedan llegar...
#2 Si claro. La última partida que tuve con una niña de 5 años, me llegó a coronar todos los peones, el osito, la figura del roscón y perdí la partida porque el perro se llevó mi rey.
#4 Bueno, omití la parte "sin jugar solo, con animales o similar" pero crep que la palabra normal de mi comentario daba pistas.
#4 ¡ah!, la clásica maniobra del perro se lleva rey. Así es como Kasparov derrotó a Deep Blue la primera vez.
#22 Ya te digo, menudo listo estaba hecho el puto Kasparov
#2 No hay ninguna regla que lo impida, podrías tener nueve damas... o diez caballos. Pero desde luego no sería una partida "normal".
#9 Me surge la duda de tener en cuenta que el rey contrario no puede estar en jaque y llegará un momento con X reinas que sea casi imposible que no lo esté y eso teniendo en cuenta que las otras piezas no hayan caído.
#11 No necesariamente... el rey rival puede (o más bien debe) estar parapetado detrás de sus piezas.
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.
Esto me recuerda a un pedazo problema que nos puso el profesor de fundamentos de la programación en la facultad en primero. Era el problema de las ocho reinas devolviendo el número de soluciones, pero en un tablero NxM (no hay problema hasta aquí, backtraking a tope y listo, además era parte de la asignatura) pero con la condición de que si M=N había que eliminar todas las soluciones simétricas (giradas en todos los planos), Vamos, que o se te aparecía la musa para encontrar algún algoritmo para eliminarlas o a guardar cada solución e ir girando la matriz (teniendo que usar otra mas temporal para comprobar), ademas de tener que ir creando una cola de matrices para tener que guardar cada solución nueva encontrada y compararla con las siguientes. Nada mal para un problema que valía 3 puntos en un examen de 2 horas. Se le fue un poco la pinza
#13 seguro que tenía truco
#13 demasiado complejo me parece a mi todo eso para ser un examen de fundamentos en primer curso.
#16 Era un gran profesor. Explicaba muy bien y ya avisaba que en sus exámenes siempre había una parte dependiente de que, como decía él, "se te apareciese la virgen". Decía que la programación y la algoritmia era saber usar y enteder una serie de métodos para resolver un problema y si era necesario inventar un nuevo método (de ahí lo de eliminar las simétricas). El resto del examen era bastante normalillo, pero si querías nota tenias que demostrar que sabías usar la cabeza para resolver un nuevo problema, más allá de lo explicado. A mi personalmente ese modo de pensar me pareció cojonudo, pero te puedo asegurar que muchos alumnos protestaron y le preguntaron que como se hacía eso, a lo que respondió "Aun me lo tengo que pensar". Un crack
#39 Parte está respondido en #30. La cursé en el año 92-93. Era anual y se complementaba con un laboratorio de programación (el primer cuatrimestre QuickBasic y el segundo Pascal). La verdad es que daban caña.
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.
#13 Puff me has recordado lo que me costó a mi aprobar la asignatura de Algoritmos y Estructuras de Datos, era con diferencia la más chunga de la carrera, al menos en la EUITIO de Oviedo donde yo estudié. La aprobé la última, por poco, y después de dedicarme un año entero sólo a ella. Eso fué en 2002, me hago viejuno...
Saludos a mi profesor, Oliverio... que majete era... siempre con una sonrisa en la cara...
#13 Yo recuerdo un examen en Diciembre de programación. De todos los que nos presentabamos, solo uno saco un 80% de la nota, dos sacaron un 40% y varios entre ello yo, un 20%. El problema valio 3 ó 4 puntos y aunque me pase una hora dandole vueltas, nada. Y luego lo repitieron en el examen de febrero de Algoritmos y Estructuras de Datos.
Creo que solo buscaban suspender al mayor número de alumnos.
#20 y por qué no vas a una tutoría a que te lo expliquen, para eso están
#23 Algunos profesores solo sabian soltar su rollo y comparar el examen con la solución que otro profesor habia propuesto...
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)?
#13 ¿En qué año la cursaste? A mi me parece algo totalmente exagerado, y seguramente propio de un mal profesor, y no creo que se pueda hacer en un tiempo razonable teniendo en cuenta que tendrías los 7 puntos del resto del examen en juego ( y que requieran su tiempo). También es un problema en el que es muy fácil confundirse con los índices y dudo que en primero sea razonable exigir backtracking, aunque depende de la intensidad horaria o d si la asignatura era anual.
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.
Doy la solución en el mensaje mil.
La noticia es falsa y sensacionalista. Ni la Universidad de Sant Andrews ofrece recompensa, ni hay recompensa de un millón por la solución de este juego.
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: https://es.wikipedia.org/wiki/Problemas_del_milenio
#32 El que dice cosas falsas y sensacionalistas eres tú (¿ves?, yo también se usar negritas)
Mira: https://www.st-andrews.ac.uk/news/archive/2017/title,1539813,en.php
#33 Se nota que no te has leido el link que has puesto, porque reafirma lo que he dicho.
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.
#33 Como ya te han comentado, al resolver ese problema de convertir un problema NP en P, se estaría resolviendo uno de los problemas del milenio. No es que se busque una solución al problema de las n reinas en concreto. En esa propia noticia que pones, cuando hablan del premio, enlazan al problema del milenio P vs NP:
«Visit the Clay Institute website for more information on the US$1m prize.»
El enlace:
http://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.»
https://theconversation.com/why-the-worlds-toughest-maths-problems-are-much-harder-than-a-chess-puzzle-and-well-worth-us-1m-83516
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
No he terminado de ver todo el vídeo porque se dedica principalmente a explicar el problema, y parece que no mucho a hablar del titular. Quizás se refiera a resolver el problema de P=NP o quizás se refiera a esta otra noticia:
https://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.
http://www.wolframalpha.com/input/?i=1000!
De matemática sabrá un güevo, pero de comunicar....menudo ladrillo de vídeo. ¿Y porqué no parpadea?
Si no hay límite de tiempo con reglas y encadenamiento hacia delante vale...
Ahora.... Va a tardar.
Madre mía, como marea el video, con el zoom palante, zoom patras... hazte un cursillo de videos, tio...
En el mundo no hay tantas monarquías para que haya 1000 reinas en el tablero, ¡Glub!, así que mejor la denominamos Dama.
A ver si lo puedo resolver yo. Ya. Siguiente problema
Voto negativo porque el problema de las 8 reinas ya esta resuelto:
https://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.
#10 Hay 10 tipos de personas en el mundo: los que saben binario y los que no.
#10 el titular dice 1000 reinas