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

1. Sobre generación de todas las permutaciones de un conjunto.

Hace unos días (casualmente justo despues de que yo publicase una entrada sobre Silicon Fjord :-)) apareció en Arxiv un enigmático artículo. Enigmático dado que no tenía fecha y además difícil de datar: la bibliografía es antigua, y tampoco el  lenguaje de programación que utilizan, Racket Scheme, es informativo al respecto.

En cualquier caso lo reseño sobre todo dada la relación indirecta de su contenido con los resultados de la patente.

Título. Rule based lexicographical permutation sequences.

Autor. Asbjørn Brændeland

Abstract. In a permutation sequence built by means of sub permutations, the transitions between successive permutations are subject to a set of n(n – 1)/2 rules that naturally group into n – 1 matrices with a high degree of regularity. By means of these rules, the sequence can be produced in O(3n!) time and O(n 3 ) space.

Bibliografía. 

[1]Heap, B. R. (1963). “Permutations by Interchanges”. The Computer Journal 6 (3): 293–4.

[2]Johnson, Selmer M. (1963), “Generation of permutations by adjacent transposition”, Mathematics of Computation 17: 282–285.

[3] Sedgewick, R (1977). “Permutation generation methods” (PDF). Computing Surveys 9: 137–164.

[4] Trotter, H. F. (August 1962), “Algorithm 115: Perm”, Communications of the ACM 5 (8): 434–435, doi:10.1145/368637.368660.

2. Big data y energía de fusión.

Título. Towards Real-Time Detection and Tracking of Blob-Filaments in Fusion Plasma Big Data. 

Abstract.

Magnetic fusion could provide an inexhaustible, clean, and safe solution to the global energy needs. The success of magnetically-confined fusion reactors demands steady-state plasma confinement which is challenged by the blob-filaments driven by the edge turbulence. Real-time analysis can be used to monitor the progress of fusion experiments and prevent catastrophic events. However, terabytes of data are generated over short time periods in fusion experiments. Timely access to and analyzing this amount of data demands properly responding to extreme scale computing and big data challenges. In this paper, we apply outlier detection techniques to effectively tackle the fusion blob detection problem on extremely large parallel machines. We present a real-time region outlier detection algorithm to efficiently find blobs in fusion experiments and simulations. In addition, we propose an efficient scheme to track the movement of region outliers over time. We have implemented our algorithms with hybrid MPI/OpenMP and demonstrated the accuracy and efficiency of the proposed blob detection and tracking methods with a set of data from the XGC1 fusion simulation code. Our tests illustrate that we can achieve linear time speedup and complete blob detection in two or three milliseconds using Edison, a Cray XC30 system at NERSC.

 3. Complejidad Paramétrica: isomorfismo de grafos.

Título. Isomorphism Testing for Graphs of Bounded Rank Width

Abstract.

We give an algorithm that, for every fixed k, decides isomorphism of graphs of rank width at most k in polynomial time. As the clique width of a graph is bounded in terms of its rank width, we also obtain a polynomial time isomorphism test for graph classes of bounded clique width.

4. Generalización de los grafos.

Una entrada en un blog de complejidad computacional.

5. Atlético Cuántico 0 – Real Clásico 1.

Entradas en blogs sobre el artículo. Una y otra (de uno de los autores).

Puedes comprar las camisetas de estos dos equipos aquí🙂.

¿ Le parecen al lector muchos 11 autores para un artículo ?. Son poquísimos.

P.s. Tengo poca afición al fútbol (salvo Mundiales) pero cuando la tenía era del Atlético. Como siempre pierde contra el Real en las ocasiones importantes, le  he puesto como perdedor. Así es la vida, estamos acostumbrados. No queremos dar a entender con esto que la computación cuántica quedará siempre también en el campo perdedor en los momentos clave.

6. Otra refutación académica de una demostación (finalmente falsa) del problema P vs NP.

En la anterior recopilación hemos comentado sobre una refutación por parte de varios estudiantes de la Universidad de Rochester.

En este caso se ha publicado en el blog de un destacado académico. El bloguero comenta que ve (entiendo que se refiere a que lee, estudia) muchas demostraciones de este tipo y que esta le ha parecido inicialmente más convincente, más seria que la mayoría de las otras.

De nuevo aplaudimos la iniciativa por parte de este académico y bloguero.

7. El problema Edit Distance (ED).

No lo conocía.

Es parecido a otros que nos han interesado y que tiene relación con nuestras investigaciones, como  el de encontrar la secuencia mínima de generadores que unen dos permutaciones (minimum length generator sequence problem,MLGS), dado un digrafo de Cayley (problema general que incluye el problema de pancake sorting, sobre el que se habla en el artículo enlazado y que es famoso dado  que Bill Gates publicó sobre él).

Recordemos que el problema MLGS se acabó demostrando que es Pspace-complete.

Extracto.

The computational complexity of the following problem is investigated: Given a permutation group specified as a set of generators, and a single target permutation which is a member of the group, what is the shortest expression for the target permutation in terms of the generators? The general problem is demonstrated to bePSppace-complete and, indeed,is shown to remain so even when the generator set is restricted to contain only two permutations. The restriction on generator set cardinality is the best possible, as the problem becomes soluble in polynomial time if the generator set cantains only one permutation. An interesting feature of this problem is that it does not fall under the headings of ‘two person games’ or ‘formal languages’ which cover the great majority of known PSpace-complete problems. 

Me pregunto si no existe algún tipo de relación entre ED y MLGS. Parece claro, al menos para mi de  manera intuitiva, que el  segundo es una restricción del primero. Corrección posterior. Para secuencias de longitud n, la mejor cota superior conocida para un algoritmo determinista es O(n^2/log2n). La longitud de la secuencia se puede comparar con el grado de la permutación y por lo tanto este comentario mio se debe de revisar. Esta información la saco del reciente artículo sobre el que hablamos al final, que se refiere a la distancia o medida de Levenshtein. Voy a ver cual es la mejor cota para la medida LCS.

Pero sigo pensando que el problema MLGS se puede entender como una restricción de ED: el vocabulario es más limitado, solo están permitidas las sustituciones y hay restricciones posicionales. El problema ED es más abierto y por eso tiene una complejidad de menor grado. El problema más restringido es más complicado. Fin de corrección.  ¿ Pero cual es la relación inversa ?.

Volviendo a ED la variante que más me gusta, de momento es la LCS. Una interesante presentación en PDF dónde hablan sobre el problema ED:  definición, aplicaciones, algoritmos. Veo que está relacionado con otra de las temáticas sobre las que hemos hablado en el blog: el lapo azul. Concretamente el problema de alinear dos secuencias de ADN se puede expresar como un problema ED.

He conocido este problema por primera vez en una entrada del blog GLL. Hablan de un artículo en el que relacionan la complejidad computacional de éste problema con la complejidad computacional de SAT.

Abstract. 

The edit distance (a.k.a. the Levenshtein distance) between two strings is defined as the minimum number of insertions, deletions or substitutions of symbols needed to transform one string into another. The problem of computing the edit distance between two strings is a classical computational task, with a well-known algorithm based on dynamic programming.

Unfortunately, all known algorithms for this problem run in nearly quadratic timeIn this paper we provide evidence that the near-quadratic running time bounds known for the problem of computing edit distance might be tight.

Specifically, we show that, if the edit distance can be computed in time O(n 2−δ ) for some constant δ > 0, then the satisfiability of conjunctive normal form formulas with N variables and M clauses can be solved in time MO(1)2 (1−ǫ)N for a constant ǫ > 0. The latter result would violate the Strong Exponential Time Hypothesis, which postulates that such algorithms do not exist.

Relacionado 1. Una explicación muy detallada sobre como se construye la tabla que se utiliza para encontrar una solución a este problema con el algoritmo de programación dinámica. La tabla es de nxm, dónde n es la longitud de la primera palabra y m la de la segunda. De ahí la complejidad cuadrática pero caso.   

Relacionado 2. Sobre Subexp.

Es un artículo que explica muy bien la problemática relacionada con éste concepto.

Título. The Prospects for Sub-Exponential Time

Fecha. 2009 o posterior.

Abstract.

This paper provides a survey of some research literature on the question of whether some NP-complete problems are easier than others. The classic open problem regarding NPcompleteness is usually framed as determining whether P = NP, that is, whether the class of problems that can be deterministically decided in polynomial time is the same as the class of problems that are non-deterministically decided in polynomial time. It is widely believed that P ≠ NP, but proof of this result remains elusive. In the decades that have passed waiting for the major open question to be resolved, some researchers have investigated the question of whether some of the NP-complete problems might be easier than others. We know that NP is a subclass of EXP – the class of problems deterministically decided in exponential time, and we expect that none of the hardest problems in NP (the NP-complete problems) are in P. Is it possible that some or all of the NP-complete problems might be in a deterministic complexity class SUBEXP, which lies between P and EXP? If we assume that the Satisfiability problem is strongly exponential, can we prove that all or some of the other NP-complete problems are also strongly exponential?

A survey of the research literature shows that there is no firm consensus on which of the hard problems are easier than the others. In this paper we examine various definitions of sub-exponential time, discuss the hypothesis that Satisfiability is strongly exponential, and review the results regarding which hard problems might be in SUBEXP. Our goal is to provide a clear summary, for both faculty and students, of research on a major open question at the center of computer science that remains intriguing and somewhat controversial, even fifty years after Stephen Cook first defined the class of NP-complete problems.

Incluye una imagen sobre como sería el mundo de la complejidad computacional con una clase Subexp.

Del mismo autor.

T. E. O’Neil,The Importance of Symmetric Representation,” Proceedings of the 2009 International Conference on Foundations of Computer Science (FCS 2009), pp. 115-119, CSREA Press (2009).

2010. On Clustering in the Subset Sum Problem

Abstract.

The research literature on NP-complete problems includes some attempts to identify easier and harder problems within the class, and the results with respect to Subset Sum are not particularly conclusive.

If the complexity parameter is the cardinality of the set S, the problem appears to be strongly exponential (as hard as any problems in the class). If the classical complexity measure of bit length of the problem input is used, however, it can be shown that Subset Sum has a sub-exponential-time algorithm. This would make it an easier problem than those that remain strongly exponential when input length is the complexity parameter.

This paper is intended to contribute evidence that Subset Sum is really an easier problem – that its apparent sub-exponential complexity is genuine and not just an artifact of an inefficient representation. We proceed by empirically examining the clustering phenomenon in the list of sums of subsets of S. When the set of integers S is dense (when the cardinality of the set is close to the maximum integer within it), we discover that almost all possible sums are covered by some subset. There appears to be a density threshold beyond which a subset with target sum t always exists for targets greater than the maximum value in S and less than the sum of all elements in S minus the maximum. The proof of such a result would provide the basis for an algorithm whose running time would remain sub-exponential even for a short, complement-based representation of a dense set. This, in turn, would solidify the argument that Subset Sum is truly an easier hard problem.

Como dicen las evidencias son empíricas.

8. Laszlo Babai, premio Knuth 2015.

Este investigador húngaro ha trabajado en temas relacionados con nuestras investigaciones y en otros menos relacionados pero que nos interesan por igual. Su página web con información sobre los temas sobre los que ha investigado.

Creo que el premio, que se otorga por toda una carrera,  es merecido. También ha recibido el Premio Godel, que se otorga por las mismas instituciones que el anterior, pero más bien por un resultado en concreto.

Extracto (del primer enlace, que explica los motivos por los que se le ha concedido el premio).

In addition to his extensive research contributions, Babai is well known for his commitment to the free flow of knowledge without geographical or economic barriers. He has spearheaded and continues to lead many efforts to make cutting-edge research accessible to all.

De manera más sustancial, en relación a su trabajo de investigación citan:

–el concepto de demostración de dificultad de aproximación;

–las demostraciones interactivas (relacionadas con el concepto anterior), demostraciones holográficas y el teorema PCP;

–el campo de property testing (chequeo de propiedades);

–su trabajo en la teoría de grupos algorítmica (esta es la parte más relacionada con nuestras investigaciones) y en concreto su aplicación al problema de isomorfismo de grafos;

–su trabajo en algorítmica en problemas de retículos;

–su trabajo par definir clases de complejidad de comunicación.

Ahí es nada…

9. Mujeres matemáticas francesas.

Extracto.

The intersection of the fields of history of mathematics and history of women is notoriously small. From Hypatia of Alexandria to Emmy Noether, very few women are known to have contributed to the development of mathematics, and the number of those born in France is even smaller. Were there any before Gabrielle-Émilie Le Tonnelier de Breteuil, marquise Du Châtelet-Lomond (1706-1749), the little-known Nicole-Reine Étable de Labrière Lepaute (1723-1788) and the even lesser known Marie Anne Victoire Pigeon d’Osangis (1724-1767)? Were there any between Sophie Germain (1776-1831) and those whose names and accomplishments will appear in this article ?

En el artículo contestan a estas preguntas centrándose en un período en concreto.

10. Algorítmica y mercados. 

Un mercado es un mecanismo social que casa oferta y demanda. Asociamos mercado con precios, pero no todos los mercados funcionan (pueden funcionar) con el mecanismo de precios. A algunos de los que no pueden se les llama mercados de emparejamiento y sobre ellos hablan en el libro que presentamos.

Who gets what and why (enlace a la página web del libro).

Presentación.

If you’ve ever sought a job or hired someone, applied to college or guided your child into a good kindergarten, asked someone out on a date or been asked out, you’ve participated in a kind of market. Most of the study of economics deals with commodity markets, where the price of a good connects sellers and buyers. But what about other kinds of “goods,” like a spot in the Yale freshman class or a position at Google? This is the territory of matching markets, where “sellers” and “buyers” must choose each other, and price isn’t the only factor determining who gets what.

Alvin E. Roth is one of the world’s leading experts on matching markets. He has even designed several of them, including the exchange that places medical students in residencies and the system that increases the number of kidney transplants by better matching donors to patients. In Who Gets What — And Why, Roth reveals the matching markets hidden around us and shows how to recognize a good match and make smarter, more confident decisions.

Nota. Ahorro al lector el comentario anti-google. Fin de nota.

Hicimos una entrada sobre este autor, que recibió un Premio Nobel por su trabajo conjuntamente con otro autor (por diseñar un algoritmo de emparejamiento).

Relacionado. Un modelo para el mercado de divisas.

El  mercado de divisas es un ejemplo de los que funcionan con mecanismo de precios.

Título. An Over-the-Counter Approach to the FOREX Market

Abstract. 

The FOREX market is an over-the-counter market (in fact, the largest in the world) characterized by bilateral trade, intermediation, and significant bid-ask spreads. The existing international macroeconomics literature has failed to account for these stylized facts largely due to the fact that it models the FOREX as a standard Walrasian market, therefore overlooking some important institutional details of this market. In this paper, we build on recent developments in monetary theory and finance to construct a dynamic general equilibrium model of intermediation in the FOREX market. A key concept in our approach is that immediate trade between ultimate buyers and sellers of foreign currencies is obstructed by search frictions (e.g., due to geographic dispersion). We use our framework to compute standard measures of FOREX market liquidity, such as bid-ask spreads and trade volume, and to study how these measures are affected both by macroeconomic fundamentals and the FOREX market microstructure. We also show that the FOREX market microstructure critically affects the volume of international trade and, consequently, welfare. Hence, our paper highlights that modeling the FOREX as a frictionless Walrasian market is not without loss of generality.

En el libro reseñado hablan sobre los defectos a los que pueden estar sujetos los mercados.

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: