Archive for the ‘COMPUTATIONAL COMPLEXITY’ Category

Otros parámetros relevantes en los casos (3,3) generados.

septiembre 24, 2017

Actualización 15 octubre 2017.

En una entrada anterior de mayo de 2016 en la que comentamos sobre una generalización al resultado de Milnor,  hacíamos el siguiente comentario.

3. ¿ No podría generalizarse esta técnica a otros casos (2-n) generalizados ?. Entiendo que como mucho a los (2-4) generados.  A partir de aquí, el tema está tan abierto que determinar los paths posibles cuando se recorres la zona en la que no se encuentra el IAS identidad, puede empezar a ser complejo. Estudiaremos los casos (2-4) generados.

En esta entrada vemos que no es el unico caso.

Fin actualización.

El teorema de Milnor sobre casos (2,3) generados, sobre el que hicimos varias entradas bastante detalladas el ano pasado (en la ultima esbozabamos una generalizacion aplicable a estos mismos casos 2,3 generados), se puede “generalizar” en otros dos sentidos: analizando casos (2,n) generados (cosa que hemos realizado tambien en anteriores entradas sobre casos 2,4 generados, 2,5 generados y 2,6 generados) o analizando casos (3,3) generados, es decir aquellos en los que los dos generadores son de orden 3.

El análisis de estos casos (3,3) generados nos hace ver que, al igual queqhay sucedia para los casos 2,3 generados, hay otros parámetros clave para determinar si existen recorridos hamiltonianos en estos casos. Es decir, el orden de los dos generadores, el orden del IAS y del DAS, el orden de la circunferencia no son suficientes.

Si los generadores son x e y, los otros dos parámetros relevantes son (xy)^n=1 y (xxyy)^n=1.

Recordamos que en los casos 2,3 generados el parametro clave era el n de la relacion (xy^2)^n=1.

El lector puede comprobarlo analizando un caso de S4 con dos generadores de orden 3, IAS6 y circunferencia 2 (y por lo tanto 1/2 entangled). El análisis de este caso es muy ilustrativo y ? seguramente ?se puede generalizar a todos los casos (3,3) generados. El tema no esta 100% claro.  Por experiencia sabemos que no conviene extrapolar demasiado lo que ocurre en casos pequenos. Lo veremos en otra entrada cuando tengamos tiempo de desarrollar el tema.

Por otra parte he visto que al igual que los casos (2,3) generados, los casos (3,3) generados han sido bastante estudiados por la teoría de grupos de principios del XX: es parte del estudio de los

grupos abstractos de tipo (l,p| q,r),

siguiendo la expresión de Coxeter. Este autor y anteriormente otros como W.A. Edington, Miller, Sinkov y otros los han estudiado.

Un artículo de principios del XXI sobre el tema:

The abstract groups (3, 3 | 3, p). 

The two-generated abstract groups (l, m | n, k) defined by presentations
(l, m | n, k) = <x, y | x^l = y^m = (xy)^n = (x^−1y)^k>i (2)
were first studied by Edington [3], for some small values of  l, m, n and k.

The notation we use was devised by Coxeter [1] and Moser [2], and has a
deeper meaning that we will not discuss here.

From now on, we will always refer to presentation (2) when speaking about (l, m | n, k).

The starting point for our discussion is Theorem 2, due to Edington [3,
Theorem IV and pp. 208210]. (Notice that there is a typo concerning the
order of (3, 3 | 3, n), and a misprint claiming that (3, 3 | 3, 3) is isomorphic
to A4.). For the convenience of the reader, we give a short, contemporary
proof.

Theorem 2 (Edington). The group G = (3, 3 | 3, n) exists for every n > 1,
is of order 3n^2, and is non-abelian when n > 1. It contains a normal
subgroup H = <x^2y, xy^2>i ∼= Cn × Cn. In particular, G ∼= C3 when n = 1,
G ∼= A4 when n = 2, and G is the unique non-abelian group of order 27 and
exponent 3 when n = 3.

(more…)

Anuncios

Digrafos de Cayley bigenerados: propiedades estructurales y dificultad de los casos.

agosto 30, 2017

Llevo un cierto tiempo pensando en el siguiente tema (realmente dos dias). Las diferentes propiedades estructurales que hemos identificado (entrelazado de ciclos, entrelazado y retorcimiento) son condiciones necesarias de dificultad pero no suficientes. Que son necesarias lo hemos demstrado en anteriores entradas. Que no son suficientes lo demuestra el hecho de que hay casos con las propiedades que no suponen dificultades.

(more…)

Casos smooth.

agosto 28, 2017

Ya lo hemos comentado en anteriores entradas. No tenemos tiempo para dedicarle a estos temas.

Pero si queremos mostrar un par de casos que ilustran el concepto de smooth o lisura en el entorno de la identidad. Y queremos mostrarlo con casos en los que ninguno de los generadores sean de orden 2. (more…)

HPC. Novedades investigacion.

agosto 20, 2017

Disclaimer. Escribimos la entrada desde el smartphone. Nos es complicado poner acentos. Pedimos disculpas al lector por ello.

Pocas entradas ultimamente eh ? Muchos motivos lo explican. Entre otros el smartphone, un autentico killer. Pero no solo esto.

Lamentablemente, pese a lo planificado tambien poca investigacion. Por los mismos motivos. Pero si he pensado mentalmente en algunos temas que queremos resumir muy brevemente en esta entrada y que desarrollaremos en otro momento. Lealos el lector como unas reflexiones no muy maduradas en voz alta que pueden ser incorrectas, sobre todo la parte que se refiere a los casos twisted.

(more…)

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

julio 9, 2017

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.

(more…)

Trade Lane Megacities & Algorítmica y complejidad computacional. Modelos económicos, su utilidad práctica y su complejidad.

mayo 25, 2017

Nota. Hemos cambiado el título en un par de ocasiones para añadir y modificar algunas palabras. Uno no sabe nunca cual es el nombre más adecuado…. Fin de nota.

0. Introducción.

En Ciencias Sociales el punto de vista desde el que se estudia un determinado problema es clave.

Y hay al menos cuatro puntos de vista posibles (los cuatro perfectamente válidos): el del actor pragmático (en economía digamos es el punto del vista del empresario o emprendedor: dada una realidad que no quiero, no puedo y no voy a intentar cambiar, como me puedo beneficiar de ella de la mejor manera posible); el del regulador (en economía sería el punto de vista del Gobierno: dada una realidad como puedo hacer que las acciones de actores pragmáticos se hagan en un marco en igualdad de condiciones); el del activista (es un actor que no toma la realidad como dato, sino que quiere cambiarla; sería por ejemplo el punto de vista de  una ONG activista en algún aspecto social) y, finalmente el punto de vista del observador teórico (es el punto de vista del Académico).

(more…)

Algorítmica y complejidad computacional. Un caso de A5 (60 vértices) sin osbtrucciones pero con obstáculos.

mayo 23, 2017

1.Estoy poniendo a prueba el método de la escalera con este caso, que que me sirve para testar varios temas:

(more…)

Algorítmica y complejidad computacional. DCBs: Algunos casos ¿ nuevos ? y ¿ difíciles ?.

mayo 21, 2017

He estado releyendo literatura más relacionada con nuestra investigación y he identificado algunos casos nuevos, que en algunos casos los autores señalan como difíciles, y cuyas propiedades estructurales quiero determinar, siempre y cuando esto no me exija reprogramar las implementaciones que ya tengo.

1. Tesis de Effler y/o Shields.

(more…)

Algorítmica y complejidad computacional. DBCs: Novedades.

mayo 20, 2017

Me está pasando una cosa extrañísima: no puedo entrar en mi blog desde ninguno de los ordenadores de mi vivienda, pero sí desde otros (desde un cibercafé).  Ni para editar ni para ver entradas. Los problemas son sólo para entrar en mi blog y en otras páginas de WordPress. Por ejemplo la páginaeffler de acceso al blog. Pero no tengo problemas para entrar en otros blogs de WordPress de terceras personas. Tampoco en otras páginas web. ¿¿??. Es decir la navegación es perfecta excepto para la página de acceso al blog de WordPress. No me explico que puede pasar. He borrado la caché, reseteado el router etc…es decir técnicas que otras veces han funcionado. Lo extraño es que pase con todos los ordenadores de la vivienda y no sólo con el que uso habitualmente.

Actualización mismo día noche: ¡ Solucionado !. Sin hacer yo nada. Otra rareza de internet que no me explico. Y no estoy pensando en ninguna “agresión” dirigida específicamente a mi vivienda. Seguramente ha sido un tema general de wordpress, pero sigo sin entender pq en el ciber si podía acceder… Paso a pulir la entrada. Fin de actualización.

En fin escribo desde un ciber. Por fin he tenido un poco de tiempo para releer entradas anteriores que listamos en una entrada anterior, y antes de que se me complique de nuevo la vida (seguramente dentro de una semana), tengo ya algunos temas completamente claros que son los que quiero publicar en esta entrada muy brevemente. De nuevo me está costando coger ritmo y no se si me va a dar tiempo en una semana a sumergirme lo suficiente en el tema como para obtener resultados tan notables como hace un par de meses más o menos. Como en esa ocasión no publicaremos todo.

Es posible que los comentarios que siguen contengan errores o inexactitudes que corregiremos cuanto tengamos acceso al blog desde el domicilio):

(more…)

Algorítmica y complejidad computacional. Muy breve historia (bibliográfica) de la teoría de grafos.

mayo 15, 2017

La primera versión, corta, de esta entrada se hizo el 15 de  mayo. Se ha actualizado para obtener una versión mas larga con actualizaciones el 16 y 17 de mayo.

(more…)