Algorítmica y complejidad computacional. Recopilación de enlaces, marzo de 2015, 1.

No estamos  escribiendo mucho sobre estos temas últimamente. Tampoco creo que escribamos con mucha más frecuencia en el futuro, aunque nunca se sabe que curso seguirá el capricho  de la curiosidad. Algunos enlaces curiosos, que me han llamado la atención.

1. Semigrupos y complejidad computacional.

Título. Semigroups and one-way functions

Del mismo autor ver también este otro paper que desarrolla el citado.

Y del mismo autor,

Título. One-way permutations, computational asymmetry and distortion.

Abstract.

Computational asymmetry, i.e., the discrepancy between the complexity of transformations and the complexity of their inverses, is at the core of one-way transformations. We introduce a computational asymmetry function that measures the amount of one-wayness of permutations. We also introduce the word-length asymmetry function for groups, which is an algebraic analogue of computational asymmetry. We relate boolean circuits to words in a Thompson monoid, over a fixed generating set, in such a way that circuit size is equal to word-length. Moreover, boolean circuits have a representation in terms of elements of a Thompson group, in such a way that circuit size is polynomially equivalent to word-length. We show that circuits built with gates that are not constrained to have fixed-length inputs and outputs, are at most quadratically more compact than circuits built from traditional gates (with fixed-length inputs and outputs). Finally, we show that the computational asymmetry function is closely related to certain distortion functions: The computational asymmetry function is polynomially equivalent to the distortion of the path length in Schreier graphs of certain Thompson groups, compared to the path length in Cayley graphs of certain Thompson monoids. We also show that the results of Razborov and others on monotone circuit complexity lead to exponential lower bounds on certain distortions.

No he leído ninguno: todos ellos muy técnicos. En éste último paper relaciona los circuitos booleanos con los elementos de monoides de Thompson: A boolean circuit is equivalent to a word over a fixed generating set of a Thompson monoid, with circuit size being equal (or linearly equivalent) to word-length over the generating set. The Thompson monoids that appear here are monoid generalizations of the Thompson group G2,1, obtained when bijections are generalized to partial functions. Recordamos que un monoide es un semigrupo con elemento neutro. Es decir, es un grupo en el que se relaja la condición de elemento inverso para todos los elementos.

Algunos enlaces y extractos comentaros que facilitarán la lectura:

–sobre los grupos de Thompson: In mathematics, the Thompson groups (also called Thompson’s groups, vagabond groups or chameleon groups) are three groups, commonly denoted F \subseteq T \subseteq V, which were introduced by Richard Thompson in some unpublished handwritten notes in 1965…All three Thompson groups are infinite but finitely presented. The groups Tand V are (rare) examples of infinite but finitely-presented simple groups. The group F is not simple but its derived subgroup [F,F] is and the quotient of F by its derived subgroup is the free abelian group of rank 2. F is totally ordered, hasexponential growth, and does not contain a subgroup isomorphic to the free group of rank 2.  Y muy interesante:

A finite presentation of F is given by the following expression:

\langle A,B \mid\ [AB^{-1},A^{-1}BA] = [AB^{-1},A^{-2}BA^{2}] = \mathrm{id} \rangle

where [x,y] is the usual group theory commutator, xyx−1y−1.

Although F has a finite presentation with 2 generators and 2 relations, it is most easily and intuitively described by the infinite presentation:

\langle x_0, x_1, x_2, \dots\ \mid\ x_k^{-1} x_n x_k = x_{n+1}\ \mathrm{for}\ k<n \rangle.

The two presentations are related by x0=A, xn = A1−nBAn−1 for n>0.

Es decir F es bigenerado.

–Sobre los grafos de Schreir (también llamados Schreier coset  graphs).

Schreier coset graph is a graph associated to a groupG, a generating set { xi : i in I }, and a subgroup HG.

The vertices of the graph are the right cosets Hg = { hg : h in H } for g in G.

The edges of the graph are of the form (Hg,Hgxi).

The Cayley graph of the group G with { xi : i in I } is the Schreier coset graph for H = { 1G },

Son por lo tanto una generalización de los grafos de Cayley. Ahorramos al lector una definición de éstos últimos. Recordamos que las técnicas de la  patente (algunas al  menos) son también aplicables a grupos infinitos bigenerados).

2. Teoria de grupos computacional.

3. Exptime y Nexptime.

En su momento nos interesaron estas dos clases de complejidad por razones relacionadas con la patente. Una pregunta y algunas respuestas sobre ellas en TCS stack exchange.

4. Superconcentrators y su relación con los expanders.

5. Otro problema GI-completo: en grafos trapezoidales.

Los grafos trapezoidales, que no conocía, tienen como subclases a los grafos de permutaciones y de los grafos de intervalos (que tampoco conocía). ¿ Existe alguna relación entre los grafos de permutaciones y los de intervalo ?

Ninguna de estas tres clases tienen sólo interés teórico. Concretamente, con respecto a los grafos trapezoidales, en el correspondiente artículo de wikipedia nos dicen:

The problems of finding maximum cliques and of coloring trapezoid graphs are connected to channel routing problems inVLSI design. Given some labeled terminals on the upper and lower side of a two-sided channel, terminals with the same label will be connected in a common net. This net can be represented by a trapezoid containing the rightmost terminals and leftmost terminals with the same label. Nets may be routed without intersection if and only if the corresponding trapezoids do no intersect. Therefore, the number of layers needed to route the nets without intersection is equal to the graph’s chromatic number. 

6. Libro: Algorithmic barrier falling. P=NP?.

El libro contiene una conversación entre un científico computacional e historiador de las ciencias computacionales y Donald Knuth, uno de los padres de la informática, sobre el que sobran las presentaciones.

No conocía este libro. Lo he visto en el blog GLL, dónde comentan sobre una parte del libro. Los comentarios de Knuth y los que se realizan en la entrada, me parecen muy relevantes para la evaluación de algoritmos que se quieran patentar por parte de los examinadores de la USPTO.

Una mejora en el tiempo de computación quizás no sea el único parámetro a tener en cuenta (por ejemplo dos algoritmos con el mismo tiempo pueden ser diferentes en cuanto a facilidad o dificultad de implementación y esto también cuenta…).

7. Nuevo (para  mi) interesante blog sobre ciencias computacionales. 

El autor es el co-autor, con Knuth, del libro citado anteriormente.  Se títula Dijkstra Rallying cry for generalization.

Muy interesante.

8. Sobre los orígenes de la teoría de la complejidad computacional.

Título. The Origins of Computational Complexity. Some influences of Manuel Blum, Alan Cobham, Juris Hartmanis and Michael Rabin

Abstract. This paper discusses some of the origins of Computational Complexity. It is shown that they can be traced back to the late 1950’s and early 1960’s. In particular, it is investigated to what extent Manuel Blum, Alan Cobham, Juris Hartmanis, and Michael Rabin contributed each in their own way to the existence of the theory of computational complexity that we know today.

Según mi experiencia la pregunta clave que intenta responder la teoría de la complejidad computacional (dado un problema computacional concreto, ¿ cual es el mejor algoritmo posible para solucionarlo ?) seguramente le ha surgido de manera intuitiva a cualquier investigador en algoritmos. Y surge sobre todo con problemas cuyos algoritmos evidentes son exponenciales, lo cual conceptualmente lleva de manera natural a la famosa conjetura. Cuando son polínomicos, son suficientemente prácticos y  te conformas con lo que tienes y punto.

Obviamente, pasar de la intuición al modelo  general y formal no siempre es fácil.  Esto es lo que hicieron estos y otros pioneros.

Extracto.

Many results of the work of Blum, Cobham, Hartmanis still influence work in the field of computational complexity that is done today. Just a few examples are: the class P of functions solvable in polynomial time defined by Cobham, the speed-up theorem developed by Blum, the concept of nondeterministic machines introduced by Rabin, and the basic concept of a `computational complexity class’ proposed by Hartmanis. These results (among much more work) provide a solid argument for the visible contribution to early computational complexity theory by the aforementioned authors. I am therefore tempted to jump to the conclusion that the field of computational complexity today would not be the same without these contributions. But this would be a wild conclusion that I could not possibly defend as there were many other researchers in the late 1950’s and early 1960’s who made major contributions that were not discussed in this paper (for example, the introduction of the notion of real-time computability around 1960 by the Japanese computer scientist Hisao Yamada [17]). Therefore, it does not seem unreasonable to assume that if the contributions of Blum, Cobham, Hartmanis and Rabin hadn’t occurred, other researchers would eventually have contributed similar results.

Al ver el título esperaba un contenido que hubiese excavado más profundamente en el pasado, a como se planteaban estas cuestiones antes de la emergencia de la informática. No obstante interesante.

9. Jevons y la teoría de la complejidad computacional.

No se dónde he leído que el economista y lógico Jevons abordó éste problema seguramente de manera intuitiva.

¿ Podría ser en su artículo On a General System of Numerically Definite Reasoning ?

O quizás se refieran a lo que comentan en Wikipedia: An example is his discussion of the use of one-way functions in cryptography, including remarks on the integer factorization problem that foreshadowed its use in public key cryptography.  Jevons estudió este problema en su libro: Principles of Science (1874).

Ponemos en marcha el radar.

10. Un historia de la teoría de la complejidad computacional. 

Escrita por un conocido bloguero (además de académico experto en estos temas). Más completa aunque empieza desde el mismo punto que la anterior.  Creo que es hasta el año 2000.

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: