Algoritmica y complejidad computacional. La complejidad de resolver el Cubo de Rubik de manera optima.

Se ha publicado recientemente un articulo sobre el tema que indicamos en el titulo.

Nota. No se muy bien como cortar y pegar un enlace en el espacio habilitado para ello en wordpress, en el smartphone.

En general hay bastantes cosas que se pueden hacer en un portatil y no se como hacer en el smartphone, o no se como hacerlo de manera rapida.

Ya he aprendido. Pero el comentario general aplica…

Otro ejemplo es marcar un bloque completo de texto, para cortar y pegar o darle el formato adecuado. Siempre se marca solo una palabra.

Ya se como hacerlo en general pero no al editar un post en wordpress. Ya se como hacer esto tambien. No era evidente.

En fin, poco a poco…

. Fin de nota.

Solving the Rubik’s Cube Optimally is NP-complete.

Erik D. Demaine∗ Sarah Eisenstat∗ Mikhail Rudoy†

Abstract.

In this paper, we prove that optimally solving an n×n×n Rubik’s Cube is NP-complete by reducing from the Hamiltonian Cycle problem in square grid graphs. This improves the previous result that optimally solving an n×n×n Rubik’s Cube with missing stickers is NP-complete. We prove this result first for the simpler case of the Rubik’s Square—an n × n × 1 generalization oft he Rubik’s Cube—and then proceed with a similar but more complicated proof for the Rubik’s.

Nuestro interes en el articulo va mas alla de lo anecdotico (el hecho de que hable de un puzzle muy conocido), y lo estamos leyendo con atencion.

En particular nos interesan en el dos puntos:

–primero, en la cadena de reducciones aparecen los hipercubos, que como es bien conocido, son grafos de Cayley.

–segundo, la reduccion lo es del problema RH a un ? problema de camino mas corto ?. Signos de interrogacion pues esto ultimo no lo tengo claro.

Por otra parte me ha sorprendido conocer que la version cuadrada es mas “compleja” que la cubica. Pensaba que era lo contrario.

Comentar que el problema se queda en NP pues el diametro del tipo de grafos que representan el problema es polinomico.

P.s. En el blog hemos publicado mucho sobre la posible complejidad computacional del problema de nuestro interes. Ya tenemos intuitivamente claro el tema. Pero solo intuitivamente. Hablo de la version normal, no de la sucinta. De ahi nuestro interes en este articulo.

Actualizaciones.

Voy a ir actualizando comentarios en esta parte. Tras lectura en diagonal todo claro hasta el punto 4.

En el punto 4, donde empieza lo que mas nos interesa todo confuso. Esto nos exige leer todo lo anterior mucho mas detenidamente. En particular el punto 2.4.

En el punto explican dos pasos de la cadena de reducciones: de grid graph a promise grid graph y de este ultimo a promise cubical graph.

En el cuatro explican la reduccion de promise cubical graph a group rubik square.  Aqui ya me pierdo completamente.

Pero la definicion de promise problem da que pensar.

Bueno ya lo he releido con mas detalle y, aunque lo tengo que releer, la idea esta mas o menos clara. De momento mas menos que mas, pero es cuestion de tiempo.

Anuncios

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: