Algorítmica y Complejidad computacional. Enlaces varios noviembre 2014.

Publico esta entrada sobre una temática que fue habitual en el blog hasta hace poco y que estamos recuperando debido al movimiento reciente relacionado con mi segunda (de  momento solicitud de) patente, cuya tramitación está ahora mismo en el momento crítico.

Muchos de los puntos son de hace meses, otros son más recientes, cómo el último o  número 10 recién salido del horno. Espero que estos contenidos no ahuyenten a muchos lectores…:-).

1. Problemas abiertos en teoría de juegos.

Hace poco hablábamos del estatus de la teoría de juegos como ciencia. Sobre lo que no había duda es que es una ciencia formal. Y una ciencia formal es interesante, desde el punto de vista de la investigación siempre y cuando tenga problemas abiertos.

En este artículo reciente (2011), escrito por uno de los investigadores destacados, Martin Shubik,  nos habla de como ve el estado actual de la disciplina y de algunos problemas abiertos.

En el punto 4.10 del artículo hablan de la relación de la Teoría de Juegos con las ciencias computacionales.  No hablan explícitamente de la complejidad computacional pero si de la explosión combinatoria (que es lo que motivó en su origen la emergencia de ésta disciplina).

Y de hecho no sólo ha habido relación interdisciplinar entre ambas, sino que esta interdisciplina tiene un nombre: Teoría de Juegos Algorítmica. Un ejemplo del tipo de temas  sobre los que trata esta disciplina (que me interesa especialmente por su relación con la ETH):

Título. Approximating the best Nash Equilibrium in n o(log n) -time breaks the Exponential Time Hypothesis

The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game initiated a quest for finding approximate Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory. We study the computational complexity of finding an ε-approximate Nash equilibrium with good social welfare. Hazan and Krauthgamer and subsequent improvements showed that finding an ε-approximate Nash equilibrium with good social welfare in a two player game and many variants of this problem is at least as hard as finding a planted clique of size O(log n) in the random graph G(n,1/2). We show that any polynomial time algorithm that finds an ε-approximate Nash equilibrium with good social welfare refutes (the worst-case) Exponential Time Hypothesis by Impagliazzo and Paturi. Specifically, it would imply a 2^O˜(n ½) algorithm for SAT. Our lower bound matches the quasi-polynomial time algorithm by Lipton, Markakis and Mehta for solving the problem.Our key tool is a reduction from the PCP machinery to finding Nash equilibrium via free games, the framework introduced in the recent work by Aaronson, Impagliazzo and Moshkovitz. Techniques developed in the process may be useful for replacing planted clique hardness with ETH-hardness in other applications

2. Relacionado con lo anterior. Una entrada en TCS sobre problemas abiertos en teoría de juegos algorítmica.

3. Aplicaciones de la teoría de juegos en Teoría Económica.

Relacionado con el punto anterior y una alguna entrada también anterior en la que hablábamos sobre las críticas a las aplicaciones reales de la Teoría de Juegos (punto 4, sobre todo el enlace a la entrevista a Ariel Rubinstein, un insider  en Teoría de Juegos) , los lectores podrán pensar que el trabajo del recientemente laureado con el Premio Nobel de Economía, Jean Tirole, es una prueba fehaciente de que las teoría de juegos tiene aplicaciones claras, en este caso en Teoría Económica.

El artículo técnico publicado por la organización del Premio Nobel sobre el trabajo de este autor parece confirmarlo.

Extracto. 

Theories of regulation and competition policy aim to provide useful scientific guidance for such intervention. Clearly, any recommendations must rest on a sound understanding of how imperfectly competitive markets work. When a firm has market power, how will it behave? How does its behavior affect the firm’s suppliers, customers, and competitors? Questions like these are studied within the field of Industrial Organization (IO). George Stigler was awarded the 1982 Prize in Economic Sciences “for his seminal studies of industrial structures, functioning of markets and causes and effects of public regulation”. Since then, however, the IO field has undergone rapid development, indeed a revolution. This revolution has greatly enhanced our understanding of imperfectly competitive markets, which in turn has laid a foundation for better informed competition policy. Comparable progress has been made in the theory of optimal regulation of firms with market power. The progress in these areas largely reflects two methodological breakthroughs: game theory and the theory of mechanism design.

El artículo es mucho  más completo que este extracto y muy recomendable para aquellos  interesados en la teoría de la Organización Industrial.

4. Un paper dónde se extraen algunas consecuencias de NEXP=EXP y de NEXP!=EXP.

5. La energía como recurso computacional.

Extracto.

There are already many ways of measuring complexity in the field of complex systems. These measures of complexity are divided into four categories by Lloyd [1]. Computational complexity is a particularly important objective to us in complex systems [2]. Certain amount of resources is necessary in order to solve any given problems. For instance, space (memory), time and energy are all essential to run an algorithm on a computer. We proposed a definition to measure the complexity of a problem: the minimum energy required to solve it [3]. This measure was based on entropy reduction (negentropy) between the entropy before the problem was solved and after, which is interesting because the definition of information is also negentropy.

6. Sobre reducciones entre problemas NPI (fuente: cstheoorystack exchange).

Una pregunta interesante y una respuesta bastante informativa.

Group Isomorphism m Graph Isomorphism m Ring Isomorphism. Also Integer Factoring mRing Isomorphism [Kayal and Saxena]. Also Graph Automorphism m Graph Isomorphism.

Not only are there no known reductions the other way, but there is provably no AC0-reduction from Graph Iso to Group Iso [Chattopadhyay, Toran, and Wagner].

Note that a reduction from Ring Isomorphism to Graph Isomorphism would also provide a reduction from Integer Factoring to Graph Isomorphism. To me, such a reduction would be surprising though perhaps not shocking.

(For Graph Automorphism vs Graph Isomorphism, their counting versions are known to be equivalent to one another and equivalent to deciding Graph Isomorphism. However, that’s not necessarily saying much, as the counting version of bipartite matching is equivalent to the counting version of SAT.)

I don’t think there is a real consensus as to which, if any, of these are actually in P. If any of these problems is NP-complete then PH collapses to the second level. If factoring is NP-complete, then it collapses to the first level, i.e. NP=coNP.

Also, I seem to recall that using techniques similar to Ladner one can show that any countable partial ordering can be embedded in the ordering m on the problems in NP (so it’s not just a hierarchy, but an arbitrarily complicated countable partial order).

7. Un problema de verificación en sistemas concurrentes reducible a problemas de grupos de permutaciones. 

Título.  A LINEAR-TIME ALGORITHM FOR THE ORBIT PROBLEM OVER CYCLIC GROUPS∗

Abstract.

The orbit problem is at the heart of symmetry reduction methods for model checking concurrent systems. It asks whether two given configurations in a concurrent system (represented as finite strings over some finite alphabet) are in the same orbit with respect to a given finite permutation group (represented by their generators) acting on this set of configurations by permuting indices. It is known that the problem is in general as hard as the graph isomorphism problem, which is widely believed to be not solvable in polynomial time. In this paper, we consider the restriction of the orbit problem when the permutation group is cyclic (i.e. generated by a single permutation), an important restriction of the problem. Our main result is a linear-time algorithm for this subproblem. Our result can also be construed as a substantial improvement of Kannan-Lipton’s polynomial-time solution to the orbit problem over rational matrices when restricted to permutation matrices. To complement this result, we delineate the boundary of tractability by showing that permutation groups generated by two permutations already suffice to make the orbit problem as hard as the graph isomorphism problem.

Más sobre los métodos de reducción en base a simetrías en verificación de modelos (model checking). Me ha interesado el asunto y me he bajado bastante documentación. Si consigo leerla y asimilarla quizás haga una entrada específica.

8. Expander CNFs have Exponential DNNF Size. 

Abstract.

We prove an unconditional exponential lower bound on the DNNF size of CNF formulas based on a family of expander graphs; thus far, only a superpolynomial lower bound was known, subject to the condition that the polynomial hierarchy does not collapse. As corollaries we obtain that, in general, negating a DNNF leads to an exponential increase in size (this was known to hold if P 6= NP), and that the language of prime implicates (PI) can be exponentially more succinct than DNNFs (this was not even known conditionally). These results settle three open problems in the area of knowledge compilation [DM02].

9. Comparando el “polinomio de ciclo hamiltoniano” con el “polinomio de la permanente”.

Recordemos que el  polinomio de la permanente cuenta el número de recubrimientos  por ciclos (no se si es  la palabra correcta castellana) de un grafo (¿ o digrafo ?) y el polinimio de ciclo hamiltoniano cuenta el número de ciclos hamiltonianos de  un grafo (¿ o digrafo ?).  Obviamente el primero incluye al segundo. Recordemos que la permanente de una matriz cuadrada se define de manera similar al determinante, con la diferencia de que en la permanente todas las sumas son positivas.   Recordemos también que si bien ambos recorren el grupo simétrico Sn (dónde n expresa el tamaño de una fila o columna de una matriz nxn), el determinante admite cálculo eficiente (polinómico) pero se piensa que la permanente no.

Extracto. (fuente)

Were one to attempt to compute determinants directly using Equation (4), then one would need to sum up n! terms, where each summand is itself a product of n factors. This is an incredibly inefficient method for finding determinants since n! increases in size very rapidly as n increases. E.g., 10! = 3628800. Thus, even if you could compute one summand per second without stopping, then it would still take you well over a month to compute the determinant of a 10×10 matrix using Equation (4). Fortunately, there are properties of the determinant (as summarized in Section 6 below) that can be used to greatly reduce the size of such computations. These properties of the determinant follow from general properties that hold for any summation taken over the symmetric group, which are in turn themselves based upon properties of permutations and the fact that addition and multiplication are commutative operations in a field F (which, as usual, we take to be either R or C).

Los métodos de descomposición (que reducen el problema al cálculo de determinantes de matrices más pequeñas) permiten calcular el determinante en O(n^3). Parece que hay un método al más eficiente  pero desconozco los matices.

A lo que iba. Un usuario de CSTheory stack exchange  hace una pregunta sobre la relación entre el polinomio de ciclo hamiltoniano (cuyo sumatorio recorre todas las permutaciones cíclicas de Sn) y el polinomio de la permanente (cuyo sumatorio recorre todo Sn).

Extracto.

Actually, why HAM is not even a non-monotone projection of PER? Over the boolean semiring, the former is NP-complete, while the latter is in P. But why? Where is a place where being cyclicfor a permutation makes it so special ?

No hay respuesta.

10. Memcomputación y complejidad. 

Terminamos  la  entrada con una curiosidad (vista hoy mismo en un blog de Ciencia que seguimos leyendo puntualmente): según afirma el bloguero, el problema P vs  NP tiene una solución sorprendente en un nuevo modelo de computación (que desconocía), la memcomputación.  La solución es P = NP.  En el primero de los dos últimos enlaces presentan el modelo y en el segundo resultados experimentales sobre la solución como se

(Nota provisional:  advierto al lector que tengo todos estos temas muy oxidados y deben de  leer lo que sigue con precaución. Estoy leyendo ahora mismo estos artículos y según leo voy añadiendo comentarios a la  nota.

Yo no tengo 100% claro de momento que afirmen esto y el bloguero hace un comentario muy atinado en este sentido. Afirman que el Modelo de Memcomputación (UMM) es equivalente al de una Máquina de Turing no determinista (NDTM), pero como es conocido, éste último no es un modelo realista de computación. Una solución al problema en el sentido indicado sería cierta si el Modelo de Memcomputación fuese equivalente a  una Máquina de Turing Determinista. El punto a destacar es que según parece defienden que las máquinas del modelo de memcomputación sí son realistas: “Most importantly, it has been proved mathematically that UMMs has the same computational power than NDTM, but unlike  the latter UMMs are fully deterministic machines and as such, they can actually be fabricated”.

En el segundo artículo  comentan:  It is worth stressing that our result do not answer the P = NP question since the latter  has its solution only within the Turing Machine paradigm.  Although a UMM is Turing-complete it is not a Turing machine.

¿ Quieren decir que una reducción o conversión de  una UMM en un una Máquina de Turing tendría un coste de tiempo exponencial ? ¿ Es esto posible entre problemas Turing completos ? Aparentemente si: To show that something is Turing complete, it is enough to show that it can be used to simulate some Turing complete system. Por lo tanto para determinar la propiedad de completitud (creo que) aquí no se aplica la otra condición, clave en teoría de complejidad computacional de  ser reducible a otro problema  en un tiempo eficiente (que varía según el nivel en el que nos situemos: polinómico si hablamos de problemas NP-completos o logarítmico si hablamos de problemas P-completos). Pero el problema P vs. NP se mueve dentro de la teoría de  complejidad computacional y se ha definido en base a Máquinas de Turing, por lo tanto entiendo que tiene todo el sentido preguntarse por la eficiencia temporal de transformaruna UMM en un máquina de Turing.

Adivino, y seguramente me equivoco que la explosión exponencial en la reducción vendría  de la propiedad que llaman information overhead.

[Actualización día siguiente: en los  comentarios de esta entrada del blog de un experto en complejidad computacional hablan sobre este modelo.  Desde el 46 en adelante. Interviene en el thread uno  de los autores. Un extracto de uno de los comentarios del experto al que ninguno de los autores ha contestado de momento: If the memcomputing model is able to manipulate exponentially-long integers in a single time step (as I understood your paper to say), then it’s going to require exponential resources to simulate the memcomputing model—not merely using a Turing machine, but using any device that we know how to implement within the physical universe. Un poco en la línea  de lo que veníamos diciendo aunque  identifica  claramente el problema. Haremos seguimiento para  ver  si contestan los autores, aunque la cosa está más o menos clara…]

Al margen de los temas  que hemos comentado, a medida  que voy leyendo y sin tener todavía claro su funcionamiento, el modelo me gusta. Me recuerda en algunos aspectos a mi propio modelo, los sistemas RH. Por ejemplo: we consider any system whose response function to any external  stimuli shows some degree of memory). En su concreción o especificación matemática (punto III) la cosa se complica.

Precisamente he estado leyendo sobre temas relacionados con las neurociencias recientemente. En fin, de confirmarse la  afirmación del bloguero, este tipo de resultados sorprendentes ya no sólo suceden en el cine :-)

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: