Archive for the ‘COMPUTATIONAL COMPLEXITY’ Category

Algorítmica y complejidad computacional. Un nuevo estilo / problema en matemáticas.

enero 26, 2017

Lo hemos comentado muy recientemente en una entrada anterior (perdón por la autocita).

Es el nuevo estilo de publicación: sin estar seguro de que lo que se tiene entre manos y publica es 100% correcto. Al igual que los problemas que se intentan resolver, las demostraciones son cada vez más complejas y necesitan múltiples mentes para la comprobación de su corrección.

Se ha publicado una interesante entrada en el blog GLL en la que hablan sobre este  mismo tema

The issue is simple:

Someone writes up a paper that “proves” that X is true, where X is some hard open problem. How do we check that X is proved?

The proof in question is almost always long and complex. So the checking is not a simple matter. In some cases the proof might even use nonstandard methods and make it even harder to understand.

y comentan sobre las posibles reacciones a este nuevo estilo de matemáticas.  Recomendamos su lectura.

(more…)

Algorítmica y complejidad computacional. Otra conjetura (dicotomia Feder-Vardi en CSPs) posiblemente resuelta.

enero 12, 2017

Es el nuevo estilo de publicación: sin estar seguro de que lo que se tiene entre manos y publica es 100% correcto. Al igual que los problemas que se intentan resolver, las demostraciones son cada vez más complejas y necesitan múltiples mentes para la comprobación de su corrección.

Me interesé en las dicotomías relacionadas con CSP en su momento, cuando estudiaba sobre temas de complejidad computacional. Esta dicotomía además tiene que ver con digrafos, en los que tenemos interés en general. Y para más inri tiene que ver con homomorfismos entre digrafos y uno de los pasos de nuestro método es precisamente un homomorfismo entre digrafos. Por lo tanto vamos a hacer seguimiento. Pero ojo, no estamos afirmando que este resultado tenga nada que ver con el nuestro.

El artículo:  Dichotomy for Digraph Homomorphism Problems

We consider the problem of finding a homomorphism from an input digraph G to a fixed digraph H. We show that if H admits a weak-near-unanimity polymorphism ϕ then deciding whether G admits a homomorphism to H (HOM(H)) is polynomial time solvable. This confirms the conjecture of Bulatov, Jeavons, and Krokhin, in the form postulated by Maroti and McKenzie, and consequently implies the validity of the celebrated dichotomy conjecture due to Feder and Vardi. We transform the problem into an instance of the list homomorphism problem where initially all the lists are full (contain all the vertices of H). Then we use the polymorphism ϕ as a guide to reduce the lists to singleton lists, which yields a homomorphism if one exists.

el blog dónde he visto la noticia.

Algorítmica y complejidad computacional. El problema P vs. NP, un survey.

enero 8, 2017

El autor del survey es el merecidamente popular bloguero (y por supuesto académico experto en computación cuántica) Aaronson.

Lo he leído muy muy en diagonal este finde aprovechando que tenía un potente resfriado, lo cual en general y paradójicamente me inspira. Me ha gustado sobre todo (y mucho) el punto 6, en el que he concentrado mi tiempo. Los otros puntos, que finalmente me he saltado, diría que no aportan demasiado a cualquiera que ya conozca el tema (aunque yo lo tengo completamente oxidado y me vendría bien un recordatorio, así que lo leeremos más detalladamente en otra ocasión).

El punto 6 repasa las barreras o limitaciones teóricas que se han encontrado (y se pueden encontrar) en los intentos de demostraciones de esta conjetura (tema muy bien explicado que finalmente creo que he comprendido, pero que nadie me pida que se lo explique ahora :-); nos demuestran que hay niveles de abstracción inadecuados o más bien insuficientes para atacar este problema, sea por exceso o sea por defecto, lo cual da que pensar; realmente los nombres elegidos para las denominarlas no dicen mucho de lo que luego son) así como algunos enfoques prometedores, que permiten saltarse estas barreras (aunque a lo mejor se encontrarán con otras) como el utilizar cotas superiores algorítmicas para demostrar cotas  inferiores teóricas y así separar clases de complejidad (método que ya ha dado sus frutos hace unos años, separando dos clases de complejidad, eso sí muy extremas; también tiene un nombre raro) o el enfoque llamado Geometric Complexity Theory que aplica técnicas de geometría algebraica (el estudio de los conjuntos de soluciones de los sistemas de ecuaciones algebraicases decir a ecuaciones polinómicas multivariables, cuando las variables recorren determinados tipos de estructuras algebraicas) a estos temas. Gracias a este survey también he comprendido este último enfoque, obviamente en líneas muy muy generales (idem, que  nadie me pida que se lo explique…).  El autor no entra en demasiados detalles técnicos al respecto, lo cual algunos agradecerán, pero nos da una visión de (un) pájaro con muy buena vista. Por lo visto a algunos expertos este enfoque les parece una complicación innecesaria; a otros un camino viable.

Espero lector, que disfrutes del  survey.

Por cierto, al leerlo me he acordado de un tema que tenemos pendiente de comprobar con respecto a nuestro método de demostración de no hamiltonicidad en casos, que bien por ser entangled o twisted, no tienen recorridos hamiltonianos, método que hemos detallado largamente en varias entradas el pasado verano: ¿ como escala este método con el tamaño del input ?.

Ya en el peor caso, sólo determinar o decidir si un caso es entangled puede ser subexponencial (cota de Landau). Si es entangled el caso es potencialmente complicado y ya podemos decidir abandonarlo sin más e identificar otro que sea potencialmente sencillo.

Pero si por los motivos que sean nos gustan sus propiedades conocidas y además queremos que tenga recorridos hamiltonianos luego hay una serie de pasos más que nos permiten demostrar que no los tiene y aplicar el  razonamiento contrapositivo, según hemos detallado en las entradas del año pasado. Así de memoria pensamos no incrementarán la cota teórica señalada en el peor caso (según pienso hablaríamos de una suma de operaciones de complejidad subexponencial, lo cual sólo añadiría constantes). Pero queremos comprobarlo.

De  cualquier manera ya la cota subexponencial peor caso sólo para decidir si el caso es entangled nos deja completamente insatisfechos…Por otra parte también hemos comentado en varias entradas anteriores que hay buenos argumentos para pensar que el caso medio no será subexponencial, sino más bien cuasipolinómico (ver también aquí), lo cual nos consuela. Por otra parte de momento no hemos investigado si hay un test más eficiente para identificar si un caso tiene las propiedades de entrelazado (entanglement) o de retorcimiento (twistedness). No me parece fácil mejorar el  estado del arte en esto, pero tampoco imposible.

Algunos extractos (barriendo para casa :-)):

 –2.2.1 Search, Decision, and Optimization . . . . . . . . . . . . . . . . . . . . . . . . 16

Es un extracto del índice. En el punto indicado nos explica la diferencia entre estos problemas (también la no diferencia desde el punto de vista de complejidad computacional). ¿ Por qué es tan complicado entender esta diferencia ?

–Just as Hilbert’s question turned out to have a negative answer, so too in this case, most computer scientists conjecture that P!= NP: that there exist rapidly checkable problems that aren’t rapidly solvable, and for which brute-force search is close to the best we can do. This is not a unanimous opinion. At least one famous computer scientist, Donald Knuth [151], has professed a belief that P = NP, while another, Richard Lipton [171], professes agnosticism.   

Desconocía esta posición de Knuth tan extrema (bastante reciente; la referencia es: D. E. Knuth and E. G. Daylight. Algorithmic Barriers Falling: P=NP? Lonely Scholar, 2014; se trata de una entrevista). Si conocía la del otro investigador pues leemos su blog. Son, dicho sea con todos los respetos, dos veteranos que ya no tienen nada que demostrar a nadie ni nada que temer y, a calzón quitao, muestran un escepticismo a contracorriente muy sano y recomendable, que equilibra la balanza. Hace poco hicimos una entrada sobre otro investigador, más joven, que también expresaba sus dudas abiertamente.

–More broadly, there are many cases in mathematics where we can prove that some object O of interest to us has a property P, even though we have no hope of finding a general polynomial time algorithm to decide whether any given object has property P, or even to certify a large fraction of objects as having property P. In such cases, often we prove that O has property P by exploiting special symmetries in O—symmetries that have little to do with why O has property P, but everything to do with why we can prove it has the property. As an example, a random graph is an expander graph (that is, a graph on which a random walk mixes rapidly) with overwhelming probability. But since the general problem of deciding whether a graph is an expander is NP-hard, if we want a specific graph G that’s provably an expander, typically we need to construct G with a large amount of symmetry: for example, by taking it to be the Cayley graph of a finite group. Similarly, even though we expect that there’s no general efficient algorithm to decide if a Boolean function f is hard,51 given as input f’s truth table, we might be able to prove that certain specific f’s (for example, NP- or #P-complete ones) are hard by exploiting their symmetries. Geometric Complexity Theory (see Section 6.6) is the best-known development of that particular hope for escaping the natural proofs barrier.

Esta es la única mención honorífica a los Grafos de Cayley en todo el survey, en un contexto perfectamente conocido desde hace años. Pero lo hemos extractado sobre todo porque es una prueba más del hecho de que demostrar que un grafo tiene determinadas propiedades, y sólo esto, añade valor. Cosa que de nuevo parece que a algunos les cuesta comprender.

–ETH is an ambitious strengthening of P!= NP. Even assuming P!= NP, there’s by no means a consensus in the field that ETH is true—let alone still further strengthenings, like the Strong Exponential Time Hypothesis or SETH, which asserts that any algorithm for kSat requires Ω ((2 − ε) n ) time, for some ε that goes to zero as k → ∞. SETH, of course, goes even further out on a limb than ETH does, and some algorithms researchers have been actively working to disprove SETH (see [275] for example).

En el blog nos hemos interesado bastante por la conjetura ETH hace años.

–But now we come to the main insight of GCT, which is that the permanent and determinant are both special, highly symmetric functions, and it’s plausible that we can leverage that fact to learn more about their orbit closures than we could if they were arbitrary functions. For starters, Per (X) is symmetric under permuting X’s rows or columns, transposing X, and multiplying the rows or columns by scalars that multiply to 1. That is, we have

Per (X) = Per ( XT ) = Per (P XQ) = Per (AXB) (2)

for all permutation matrices P and Q, and all diagonal matrices A and B such that Per (A) Per (B) = 1.

The determinant has an even larger symmetry group: we have

Det (X) = Det ( XT ) = Det (AXB) 

Nos gusta la simetría. Muy interesante. En esto se basa todo el enfoque GCT, al parecer.

Algorítmica y Complejidad Computacional. Recopilación de enlaces, noviembre 2016: Redes de Interconexión, Grafos de Cayley, Recorridos Hamiltonianos, Permutaciones y otros. 

noviembre 30, 2016

Una recopilación de artículos sobre los temas que aparecen en el título, realizada en fechas varias, la última esta misma mañana (por el lunes), en la cual he encontrado cosas muy interesantes con respecto a potenciales aplicaciones. Aunque ya se sabe que entre la ingeniería apegada a la tierra y las elevadas matemáticas se encuentra el limbo de potenciales aplicaciones que nunca terminarán de concretarse en sistemas reales.

Antes de empezar con los enlaces un extracto de una muy reciente entrada en un blog de un experto en complejidad computacional. Creo que es reseñable ya que la declaración es sorprendente, contundente y va contracorriente:

The bottom line of this post is that we can’t prove lower bounds because they are false, and it is a puzzle to me why some people appear confident that P is different from NP.

Añadido a última hora.

On the Complexity of the Word Problem of Automaton Semigroups and Automaton Groups

I. Enfoque de ingeniería de redes: redes de interconexión (supercomputadores, NoC´s, Data Center Networks).

Data center interconnection networks are not hyperbolic

David Coudert1,2 and Guillaume Ducoffe2,1 1 Inria, France 2Univ. Nice Sophia Antipolis, CNRS, I3S, UMR 7271, 06900 Sophia Antipolis, France

Abstract Topologies for data center networks have been proposed in the literature through various graph classes and operations. A common trait to most existing designs is that they enhance the symmetric properties of the underlying graphs. Indeed, symmetry is a desirable property for interconnection networks because it minimizes congestion problems and it allows each entity to run the same routing protocol. However, despite sharing similarities these topologies all come with their own routing protocol. Recently, generic routing schemes have been introduced which can be implemented for any interconnection networks. The performances of such universal routing schemes are intimately related to the hyperbolicity of the topology. Roughly, graph hyperbolicity is a metric parameter which measures how close is the shortest-path metric of a graph from a tree metric (the smaller gap the better). Motivated by the good performances in practice of these new routing schemes, we propose the first general study of the hyperbolicity of data center interconnection networks. Our findings are disappointingly negative: we prove that the hyperbolicity of most data center topologies scales linearly with their diameter, that it the worst-case possible for hyperbolicity. To obtain these results, we introduce original connection between hyperbolicity and the properties of the endomorphism monoid of a graph. In particular, our results extend to all vertex and edge-transitive graphs. Additional results are obtained for de Bruijn and Kautz graphs, grid-like graphs and networks from the so-called Cayley model.

–Muy interesante. Y muy reciente, de 2016.

The Influence of Datacenter Usage on Symmetry in Datacenter Network Design

Alejandro Ericksona , Iain A. Stewarta,∗ aSchool of Engineering and Computing Sciences, Durham University, South Road, Durham DH1 3LE, U.K.

Abstract We undertake the first formal analysis of the role of symmetry, interpreted broadly, in the design of server-centric datacenter networks. Although symmetry has been mentioned by other researchers, we explicitly relate it to various specific, structural, graph-theoretic properties of datacenter networks. Our analysis of symmetry is motivated by the need to ascertain the usefulness of a datacenter network as regards the support of network virtualization and prevalent communication patterns in multi-tenanted clouds. We argue that a number of structural concepts relating to symmetry from general interconnection networks, such as recursive-definability, the existence and dynamic construction of spanning-trees, pancyclicity, and variations of Hamiltonicity, are appropriate topological metrics to use in this regard. In relation to symmetry, we highlight the relevance of algebraic properties and algebraic constructions within datacenter network design. Built upon our analysis of symmetry, we outline the first technique to embed guest datacenter networks in a host datacenter network that is specifically oriented towards server-centric datacenter networks. In short, we provide the graphtheoretic foundations for the design of server-centric datacenter networks so as to support network virtualization and communication patterns in cloud computing.

Extractos.

Whilst the design of DCNs is more recent, it has much in common with general interconnection network design yet there are profound differences too, prompted by, for example, usage, scale, and packaging. Hitherto, the most common metrics used for DCN evaluation are the availability of routing algorithms, hardware cost (e.g., number of servers and switches), hardware complexity (e.g., number of server-ports), diameter, bisection width, connectivity, and shortest-path lengths. It is probably fair to say that the development of appropriate topological metrics for DCNs is not as advanced as it is for distributed-memory multiprocessors and networks-onchips, and that the validity of these topological metrics within a datacenter environment is not as well established. Our paper seeks to strengthen the role of topological metrics in DCN design.

Our work sits between the engineering process of building datacenters and the theoretical consideration of abstractions of DCNs as discrete structures; that is, it is graph theory targetted towards a practical application area.

(more…)

Caso de S5 2-4 generado retorcido o twisted.

junio 21, 2016

Actualización 18 de julio: he detectado un error en el punto 1. En breve lo modificaré, incluyendo seguramente las imágenes (ahora tengo el ordenador con algún problema en el modulo de electricidad). Fin de actualización.

Actualización 20 de julio. ¡¡ Corregido !!. Esta corrección nos ha obligado a borrar parte del texto que habíamos escrito, redundante. Y he cambiado la imagen. Fin de actualización.

En la entrada anterior hemos analizado un caso de S5 2-4 generado entrelazado o entangled que no sólo tenía RHs en dos de los VFs posibles (y eran 7) y hemos determinado el mecanismo que hace que los que no tienen RH no puedan tenerlo y lo que es más importante hemos demostrado que el que este mecanismo sea posible es debido a que el caso es entrelazado. Y también hemos comentado que este mecanismo no podría ser el motivo de que los casos twisted no tengan recorridos hamiltonianos.

¿ Podemos encontrar un mecanismo similar para los casos twisted, mecanismo en el que se vea claramente que puede intervenir por ser twisted ? Esto es lo que vamos a intentar contestar en esta entrada.

Para ello en esta entrada analizamos dos casos. Aunque los dos casos son twisted lo son de manera diferente: el primer caso es más cerrado, los IASes que lo hacen twisted están más cercanos el uno del otro, que en el segundo. Esto tiene consecuencias: si bien, como veremos, en los casos twisted más cerrados el método de activar el ciclo de C4 de todas las maneras posibles y concluir que todas llevan a contradicción funciona de manera bastante directa en los otros casos, los más abiertos, no parece ser así (es lo que queremos determinar).

En los casos twisted del segundo tipo, más abiertos, al aplicar el algoritmo de la patente, ocurre lo que explicamos a continuación. Primero una muestra gráfica, ya que lo hemos dibujado completamente. Sus parámetros son S5, G5, C2C4, IAS5, Circunferencia 6. Figura en la imagen siguiente (de nuevo bastante confusa, pido disculpas por ello):

s5 c2 c2 ias 6 twisted para blog

Sus VFs (excluimos los que sabemos, por el teorema de Rankin, que no pueden tener RHs). Son 23541 y 54123. Al aplicar el algoritmo que hemos implementado (el reflejado en la primera patente) determina que no tiene RHs en ninguno de estos dos vértices, pero dato importante, necesita respectivamente 27 opcions (y 11 llamadas de backtraking) y 42 opciones (y 18 llamadas de backtraking).

Creo relevante señalar a este respecto que en los otros dos casos en los que hemos encontrado demostraciones cortas o más directas de que no podían existir RHs (todos los 2-3 generados; algunos de los 2-4 generados entangled), el algoritmo identificaba que no existían sin opciones…

Otra de las preguntas que nos hacemos en esta entrada es si, en estos casos, hay una demostración más directa, más rápida, más económica, más corta, más comprensible, de que no tienen RHs en los VFs o sólo podemos determinar esto ejecutando todas estas llamadas de backtraking.

En cualquier caso queda claro lo que buscamos: identificar un mecanismo que esté relacionado con la propiedad de ser twisted y que  haga imposible la existencia de un RH en todos o algunos de los VFs. Y es muy posible que el hecho de que los ciclos de orden 4 se deban de activar de una determinada manera (que haya restricciones al respecto) forme parte del mecanismo. Y esto explica también por que el algoritmo necesita tanto backtraking en estos casos: esta propiedad no está incorporada en la implementación.

1.Twisted cerrados. A estos efectos comenzamos analizando un caso twisted cerrado que como veremos admite una demostración de que no contiene RHs sin necesidad de utilizar el algoritmo. Es aplicando aplicando el método que ya describíamos en la descripción de la patente, que consiste en activar de todas las maneras posibles el ciclo de C4 que sale de la identidad.

Es un caso 2-4 generado e IAS de orden 6 y circunferencia de orden 3 (¿ 6 IASes ?), en el que se detectaba que no podía tener recorridos hamiltonianos de manera más rápida que aplicando el algoritmo.

En un segundo punto aplicaremos este método (que ya hemos comentado que no nos satisface del todo, estamos convencidos de que debe de haber un método todavía más directo) al caso abierto, el que ha motivado la entrada para ver si funciona también. Por cierto, en breve aplicaré a este caso el algoritmo para ver tras cuantas opciones determina que no contiene RHs.  

Actualización 27 de junio de 2016. Ya lo he aplicado: salvo en el VF 31425, en el que determina que no hay VF tras 3 opciones y una llamada a backtraking en los otros lo encuentra de manera directa tras entre 1 opción (en el otro ciclo potencial y 3 op). De ciclo a ciclo el número de opciones es 3, 3,2,2,2,1. Fin de actualización.  

El caso aparece en la imagen siguiente (no está completo).

caso c2 c4 circ 3 twisted

El método es como sigue:

–el ciclo de orden 4 que sale de la identidad se puede activar de 16 maneras posibles diferentes. Algunas son equivalentes.

primera manera de activarlo: todos inactivados. Como se puede ver se genera contradicción (aparecerían necesariamente ciclos de orden 2). Esto es independiente de la propiedad de twistedness. Esta clase de equivalencia contiene solo un representante.

segunda manera de activarlo: sólo 1 activado (y por lo tanto los otros tres inactivados). En esta clase de equivalencia hay 4 representantes o maneras posibles de activar.  Y es fácil ver que se genera también necesariamente contradicción, de manera independiente a la propiedad de twistedness.

tercera manera de activarlo: tres arcos activados, también con cuatro representantes.  En la imagen siguiente (que representa el último digrafo mostrado anteriormente pero de manera más clara, sin confusión de colores) mostramos la situación cuando se activa el IAS de la identidad tomando como VF la permutación 13254. Esto hace que el ciclo de orden 4 que sale de la identidad se active por dos arcos. En esta situación todavía no se genera ninguna contradicción.

c2c4 ias 6 nuevo para blog

En la imagen se aprecia claramente que al ser twisted, el IAS marcado con A1 conecta con el IAS marcado con A2 y con el marcado como A3 y que también A2 y A3 están conectados. Lo  mismo sucede con los IASes marcados B1, B2 y B3 o los IASes marcados C1,C2 y C3. Y falta un último “cluster” o grupo de IASes que no hemos dibujado de momento para no añadir más confusión. En un caso smooth estas conexiones entre estos IASes no existirían. Es importante que el lector recuerde esto ya que estas conexiones que sólo existen por ser twisted son clave, como veremos.  

En la imagen siguiente vemos  que pasa al activar el tercer arco del ciclo de orden 4. Nótese que si activasemos estos tres arcos del ciclo de orden 4 directamente, llegaríamos a la misma situación que aparece en la imagen.

cntradiccion 200

El marcar el tercer arco tiene consecuencias:

–aparece un posible ciclo de orden 4 (marcado en la figura cómo Contradicción 1) en el que hay tres arcos ya marcados, posible ciclo que hay que corregir.

–aparece otro posible ciclo de orden 4, marcado como contradicción 2.

Si dibujamos el IAS rojo, y extraemos las correspondientes consecuencias aparece otro ciclo de orden 4, en este caso ya inevitable. Se concluye que no puede existir un RH si marcamos los 3 arcos del ciclo de orden 4 de la identidad.

Nota. Según recuerdo el primer digrafo de este caso, el que realizamos hace años y publicamos hace un par de días un poco más arriba en esta misma entrada, contiene exactamente el numero de IASes necesario para demostrar que surge contradicción en cualquiera de las activaciones posibles del ciclo de orden 4 de la identidad. En este caso contiene casi tantos IASes como el total de IASes del digrafo, lo cual no parece una gran ventaja: pero ¿ y si en los casos twisted, a medida que n crece el la contradicción se puede seguir encontrando activando un número de IASes limitado del entorno de la identidad ? . En este caso nadie diría que el método no es ventajoso…Por eso me interesa determinar si también en los casos twisted pero más abiertos, el test es local.

Fin de nota.

De la misma manera que hemos demostrado con todo detalle que emerge contradicción al marcar los 3 arcos del ciclo de orden 4 de la identidad, se podría demostrar que pasa lo mismo con cualquier otra activación de tres arcos de este ciclo (y de cualquier otro), así como al activar sólo dos arcos opuestos en el ciclo de orden 4.

Y es fácil ver de que la causa de todo esto es que el caso sea twisted.

Continuará…

Nota.

Aprovecho para hacer un apunte rápido sobre una pregunta que hicimos en una entrada anterior, a la que asociamos una figura que volvemos a publicar:

smoothes twisted

Cuando construimos el entorno de la identidad puede, en teoría suceder dos cosas: quedan todos los vértices del entorno saturados (es decir de todos ellos entran y salen 2 arcos) o no quedan saturados. En el caso de que queden saturados es fácil demostrar que casos como el de la figura no pueden suceder: supongamos que un IAS de la circunferencia que se encuentre fuera del entorno de la identidad enlaza con un IAS que se encuentre al otro lado del entorno y que en su mismo lado podemos añadir más IASes a la circunferencia. Entonces por simetria debería de entrar en el entorno de la identidad un arco de alguno de estos IASes, lo cual es contradictorio con el hecho de que está saturado. Por lo tanto cuando el entorno de la identidad queda saturado podemos afirmar que el caso será smooth.

Queda por determinar:

–si es posible construir el entorno de la identidad sin que quede saturado;

–si esto fuese posible, que formas posibles pueden adoptar estos casos;

–y si estas formas tienen consecuencias de cara al problema  de recorridos hamiltonianos.

Haremos una entrada específica para comentar sobre todo esto en detalle.

Fin de nota.

2. Twisted más abierto (realizada a partir de 27 de julio de 2016).

Ya hemos comentado que si bien en el caso twisted más cerrado estudiado en el punto 1, cuando se le aplica el algoritmo, se puede determinar que no tiene RHs en pocas opciones (entre 3 y 1) y con pocas llamadas a backtraking (en general ninguna, lo determina directamente) en el caso twisted más abierto que estamos estudiando ahora, cuando se le aplica el algoritmo, tarda bastante más en determinar que no tiene RHs: más de 20 opciones y más de 11 llamadas a backtraking.

Luego es mucho más interesante encontrar una demostración lo más directa posible en estos casos. Diría que la vía de ataque tiene que implicar el IAS de la identidad y el IAS opuesto al de la identidad en la circunferencia.

A continuación dos imágenes que muestran el caso que estudiamos. La primera ya está publicada en esta misma entrada. La segunda es un nuevo dibujo que realmente tampoco mejora mucho en términos de claridad pero al  menos nos da otra perspectiva.

s5 c2 c2 ias 6 twisted para blog

c2c4 IAS5 para blog 22

 Ver entrada con mismo título, nº2.

Historia de la teoría de la complejidad computacional: nuevos primeros pasos.

mayo 31, 2016

A raíz de la entrada anterior, en la que hablábamos de Yves Lecerf, y su contribución a las ciencias computacionales, he encontrado este enlace a un capítulo de un libro en el que hablan sobre temas que hoy se incluirían dentro de la teoría de complejidad computacional, pero en realidad antes de que ésta disciplina existiese.

Curiosamente el capítulo del libro (de 1968, año complejo en Francia en otros aspectos), se titula Complexité y el contenido, como ya hemos comentado, es sobre los problemas de complejidad computacional: explosión combinatoria etc…Como veremos el artículo que de alguna manera creó la disciplina como un ente autónomo es de 1965 lo cual explica el uso de estos nombres.

La lista de nombres que aparecen en una historia de la complejidad computacional en el ámbito anglosajón (es decir EEUU; el enlace lo es a un artículo sobre la historia de la teoría de la complejidad computacional, fundamentalmente en EEUU, escrita por uno de sus protagonistas, que además es uno de los editores del primer blog que empezó a publicar sobre estos temas, bien conocido) suelen comenzar con Hartmanis y Stearns (1965), Cobham (1964), Edmonds (1965) y ya, cuando la disciplina madura y toma plena forma, Levin, Cook (la visión de Cook, escrita en 1983; habla de un artículo de Bennett de 1962: Bennett, J. H. On Spectra. Doctoral dissertation, Department of Mathematics, Princeton University, 1962) y Karp con sus bien conocidos respectivos resultados. También se suele / puede incluir a Rabin (1959) como precursor.

Tanto Hartmanis (Hartmanis, J. January 1981. Observations about the development of theoretical computer science. Annals of the History of Computing, Volume 3, Number 1, pp. 42-51. ) como Stearns han escrito sus respectivas versiones del periodo en el que fueron protagonistas.

En otras tradiciones como la soviética, como mucho se remontan a los 50 (Trakhtenbrot, de este mismo autor es la historia de la teoría de la complejidad computacional en la Unión Soviética que aparece en el enlace anterior, titulada A Survey of Russian Approaches to Perebor (Brute-Force Search) Algorithms ). Por cierto Levin pertenece a esta otra tradición, sobre la que hablaremos luego de nuevo.

Nota. Cabe preguntarse en que medida el interés que surgió en paralelo en estos temas a uno y otro lado del telón de acero fueron producto de la Guerra Fría. Llama por ejemplo la casi total ausencia de europeos occidentales entre los pioneros. También por su diferente recepción a uno y otro lado.

Extracto.

It is not surprising that we were attracted by the same problems as our colleagues in the West (of course, we were working independently and in parallel), and we worked out almost the same techniques: complexity measures, crossing sequences, diagonalization, gaps, etc. All of these ideas arose quite naturally; we became most excited, and they evoked in us enthusiasm similar to that described by Hartmanis in his historical account (1981).

Fin de nota.

En el artículo sobre el que hablamos desde el principio nos hablan de otras épocas y otros nombre que no había visto asociados a esta disciplina:

(more…)

Dígrafos de Cayley (2,3)-generados (y otros similares): sus propiedades de hamiltonicidad.

mayo 18, 2016

Entrada en construcción. Estará terminada cuando desaparezca este mensaje.

Actualizado 18 de agosto 2016: se han añadido datos a los C2C4 generados. A falta de los de S6, la información está completa (todos los casos dibujados; no he añadido de momento los dibujos). Fin de actualización.

Actualización 8 de mayo de 2016.

Añadida información relativa a casos C2C4 de S4 (3 casos) y un dibujo más (que ya tenía realizados de hace años y he encontrado ayer revisando mis archivos) de 1 caso de S5.

Fin actualización.

http://www.famnit.upr.si/files/zakljucna_dela_repo/48

https://books.google.es/books?id=d5PLBQAAQBAJ&pg=PA224&lpg=PA224&dq=solvable+groups+permutation+generators&source=bl&ots=CGTnfchuwD&sig=i16JVQOO-SlCyuJMv0HgTVqVFpY&hl=es&sa=X&ved=0ahUKEwiP07-asfHMAhWJ2RoKHRUvAUM4FBDoAQgzMAM#v=onepage&q=solvable%20groups%20permutation%20generators&f=false

 

En base a las entradas anteriores en esta entrada quiero analizar las propiedades de hamiltonicidad de todos los casos de que dispongo (2-3) generados.

También analizaremos otros casos (2-n) generados de S5 cuyas propiedades estructurales no analicé en detalle en su momento. El factor común de todos ellos es,

–primero, que uno de los generadores es una involución y por ello en la base de datos que elaboré aparecían como entrelazados o entangled. Pero algunos de ellos o incluso que no haya recorridos en ninguno es posible

–segundo que el tamaño del IAS es “grande” en relación con el número de vértices o bien el orden del generador que no es de orden 2 es grande también.

–tercero, son casos problemáticos, en el sentido de que tienen algunos vértices finales posibles sin recorridos hamiltonianos, o incluso ninguno de ellos los tiene.

La motivación de esta entrada es la siguiente:

quiero averiguar si, como pienso, las propiedades estructurales que hemos reflejado en la patente (2º solicitud de patente) explican todos los casos complicados. Si no he analizado mal el caso de la entrada anterior (el PSL(2,7), que tengo pendiente de reanalizar) podría ser smooth y no tener recorridos hamiltonianos en ninguno de los vértices finales posibles. Realmente no hace falta analizarlo con mayor profundidad: es twisted, como todos aquellos cuya circunferencia es de orden 2 (4 IASES) si el IAS es par o de orden 4 (4 IASES) si el IAS es impar.

No obstante sí me interesa analizar varios otros de estos casos y similares, dado que es posible que tengan propiedades estructurales que nos permitan predecir mejor sus propiedades de hamiltonicidad.

Nota. El lector que haya seguido estas entradas a lo mejor se habrá realizado algunas preguntas sobre la propiedad smooth/twisted. Por ejemplo:

(more…)

Algoritmica y complejidad computacional. Algunos resultados sobre permutaciones.

marzo 13, 2016

Disclaimer. Esta entrada se ha escrito en los días 13 y 14 de marzo de 2016. La parte dónde comentamos sobre resultados de otros autores, más  el día 13; la parte más de “investigación” propia o en la que comentamos sobre nuestra propia investigación más el día 14. Recordamos una vez, con una imagen más lo que dijo Donald Knuth, uno de los padres de la informática sobre el problema que hemos estudiado y algunos de cuyos resultados estamos intentando patentar en EEUU desde hace años, con grandes dificultades en la concesión, que se deben a motivos que desconocemos, pues incluso en un mundo post Alice Corp, se deberían de poder patentar.        

Ignacio Reneses. Knuth TAOCP.

Y recordamos lo que ha comentado un investigador recientemente al respecto, investigador que utilizando uno de los pasos que quiero patentar ha dado respuesta a uno de los problemas “abiertos” en digrafos de Cayley Bigenerados:

The Hamiltonicity of G(n) was first considered by Nijenhuis and Wilf (Exercise 6 in [5]). A general condition by Rankin [7] forbids Hamilton cycles in G(n) for even n ≥ 4 (see Swan for a simplified proof [11]). Determining if Hamilton cycles exist for odd n was given a difficulty rating of 48/50 by Knuth, making it one of the hardest in The Art of Computer Programming (Problem 71 in Section 7.2.1.2 [4]).

.  

Si mis resultados aportan tanta luz a todos los casos posibles (todos los pares posibles) del problema de recorridos hamiltonianos (ciclos y caminos) en Digrafos de Cayley bigenerados, siendo un problema con una de reputación de ser tan complicado, incluso si hablamos de un solo caso, de un solo par, ¿ por que no se ha concedido la patente para los pasos solicitados directamente y está costando 8 años de tramitaciones ?. ¿ Por qué tengo, a lo mejor (esta semana saldremos de dudas)  que volver a explicar esto una vez más oficialmente al examinador pagando, seguramente, otra importante cantidad a mi agente de patentes en EEUU (no me quejo por ello; hacen bien su trabajo) ?. ¿ Por qué un problema que es tan complicado para uno de los padres de la informática (y para cualquiera que intente abordarlo sin las técnicas de la patente) no lo es para la USPTO ? ¿ Sólo porque la solución es sencilla de programar ? 

Fin de disclaimer.

Quería reflejar en esta entrada, muy brevemente,

–en el primer punto algunos resultados sobre la teoría estadística de permutaciones (propiedades de una sola permutación elegida aleatoriamente en un grupo dado, en general Sn) y algunos problemas de la teoría estadística de permutaciones (propiedades de dos permutaciones, relacionados con la segunda patente, con nuestra propia investigación) que nos gustaría ver resueltos (en algunos puntos esbozamos soluciones). En esta parte seguramente nos repetimos, pues a medida que la voy escribiendo voy acordándome que igual hay una entrada anterior de contenido similar (en cuanto a algunas preguntas; la novedad de esta entrada serían las respuestas): 8 años, que es lo que están tardando en tramitar la USPTO mis solicitudes dan para olvidar.

–en el segundo punto, la importancia de la representación de grupos de permutaciones y en el tercero una simple curiosidad, la relación del problema del Sudoku generalizado con el problema de encontrar ciclos hamiltonianos en grafos generales.

1.Teoría estadística de permutaciones: propiedades de una sola permutación.

En general la teoría estadística de permutaciones se refiere a las propiedades que podemos esperar que tenga una sola permutaciónen general elegida de manera aleatoria.

Como el lector sabe, en el resultado de la patente nos hemos interesado más en identificar determinadas propiedades que puedan tener pares de permutaciones, y sus consecuencias de cara a la solución del problema de recorridos hamiltonianos. Como veremos ya se ha trabajado bastante también en problemas relativos a pares de permutaciones (por ejemplo el resultado de Dixon, sobre el que hablaremos más adelante).

Empezamos con el artículo relevante de wikipedia que

(more…)

HPC & Algorítmica & complejidad computacional. Recopilación de enlaces, febrero 2016.

febrero 13, 2016

Una serie de enlaces sobre los temas sobre los que tratamos en esta serie.

En uno desarrollo mi opinión sobre el reciente resultado en Go. Mi conclusión es que, aunque el avance es real, no es más que incremental, y por lo tanto no es más que otra operación de marketing de Google. Y aparentemente el mercado así lo ha entendido también: tras un subidón en bolsa, ha vuelto a bajar para estabilizarse en un determinado nivel.

Quizás los compradores que están evitando la caída libre de este valor estén apostando por otro próximo subidón en marzo, cuando Alphago se enfrente a Lee Sedol (serie de partidas previstas para entre 8 y 15 de marzo; ¿ hay intencionalidad cronológica ?: la presentación de resultados del primer trimestre / 1Q es en general, creo, en la primera quincena de abril; si ganan la partida, pueden tapar unos malos resultados; si pierden, tampoco se lo va a tener nadie en cuenta…).

Esto es obviamente absurdo a cualquier plazo que supere este mes de marzo del año corriente: gane o pierda, lo que está claro es que la empresa Google (grupo Alphabet) es manifiestamente incapaz o bien de incorporar los avances en IA para mejorar la tecnología de su negocio nuclear (el buscador) o bien cuando los incorpora lo empeora, de tal manera que su buscador falla más (falsos positivos, inflación artificial de resultados de búsqueda mediante búsquedas inversas automatizadas etc…) que una escopeta de feria.

Es cada vez más un buscador…¡¡ de ruido !!.

1. Big data & discrete math.

2.MASETH y AMSETH refutadas.

Son versiones más fuertes que NSETH, SETH o ETH. Por lo tanto podría darse el caso que MASETH y AMSETH sean falsas pero las otras verdaderas.

Pido disculpas al lector (en singular: no espero que lo lea más de uno, por no explicar las siglas…).

Relacionado. Complete Problems of Propositional Logic for the Exponential Hierarchy. 

Relacionado. Polynomial Depth, Highness and Lowness for E.

3. Redes de interconexión. Una entrevista al CTO de Cray.

4. ¿ El estancamiento en supercomputación ?

Disclaimer. Que enlace a un artículo de este autor no quiere decir ni que me interesen en general los temas sobre los que hable ni que esté de acuerdo con los contenidos de sus publicaciones. Es más cuando los leo, que no siempre, suelo estar en completo desacuerdo. Esto no es necesariamente aplicable a este caso. 

5. Grafos de Cayley y Grafos de Johnson.

As an application, we determine which Johnson graphs are Cayley graphs.

Nos hemos interesado por este tema hace poco.

(more…)

O($).

enero 20, 2016

(more…)