6

Un millón de dólares para quien resuelva este “simple” enigma de ajedrez

30 visitas

|

votos: 5 · 1

|

karma: 81

|

El Instituto Clay de Matemáticas, un centro de estudio de las matemáticas estadounidense, ofrece un millón de dólares (840.000 euros) a quien resuelva un "simple" enigma de ajedrez de más de un siglo de existencia. 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.

matematicas, ajedrez, problema

comentarios (1)

#1 Deuvede

Es uno de los enigmas del milenio conocido como de P vs NP (en.wikipedia.org/wiki/Millennium_Prize_Problems). Y es uno de los problemas de lógica computacional que no se han podido resolver.

Los problemas de tipo P son aquellos que tienen una solución de coste polinómico (o sea, que a más grande el problema, el tiempo que se necesita crece linealmente).

Los problemas de tipo NP son problemas que se caracterizan por que, dada una posible solución, tardan un tiempo polinómico (P) en saber si la solución es válida. Todos los problemas NP tienen un número exponencial de soluciones en función del tamaño del problema (o sea, si el problema es el doble de grande, el número de soluciones se eleva al cuadrado). Así, la solución general de un problema NP es generar todas las posibles soluciones y testar cada una de ellas (cada test es de coste P) hasta dar con una (si necesitamos una) o probar todas las combinaciones para hallar todas las soluciones. Como hay un número exponencial de soluciones, ejecutamos un algoritmo de coste P un número exponencial de veces, lo que nos lleva a un coste exponencial.

Básicamente, si se resolviera y se demostrara que P = NP, se habría encontrado un algoritmo que resuelve de manera muy eficiente problemas que, hasta ahora, requieren de años de computación para encontrar solución (o sea, que resuelva los problemas de NP con coste P). La otra posibilidad es que se resuelva y se demostrara que P != NP, en cuyo caso se estaría seguro de que no existen soluciones más eficientes para los problemas NP que las que ya se conocen.

Finalmente, conviene comentar que todos los problemas NP están relacionados entre ellos. O sea, los ejemplos de problemas NP no son sino diferentes maneras de plantear el mismo problema computacional. Eso quiere decir que, si se encontrara una solución de coste P para uno de ellos (eg: el problema de las damas en un tablero N x N casillas), esta solución es fácilmente transformable para resolver cualquiera de los otros ejemplos de NP.

Para saber más sobre el tema de P y NP:
es.wikipedia.org/wiki/Clases_de_complejidad_P_y_NP

3 k 59

comentarios cerrados

suscripciones por RSS

ayuda

+mediatize

tendencias
postits
blog
imágenes
síguenos en:

estadísticas

mediatize

condiciones legales, de uso y de cookies | quiénes somos | licencias: código, gráficos, contenido | HTML5 | código fuente