Algorítmica y complejidad computacional. Recopilación abril 2015.

En este edición hablamos en varios puntos sobre el nuevo resultado relacionado con la Jerarquía Polinómica (PH), sobre el que el lector ya habrá oído hablar: se ha demostrado infinita bajo oráculos aleatorios (un interrogante que algún investigador se hizo hace unos treinta años y ha estado abierto hasta este mes de 2015). 

1. Multi-Broadcasting under the SINR Model.

Interesante, relacionado con los sistemas RH.

Relacionado. Otro problema con multiagentes: Byzantine Gathering in Networks.

2. Physics in 100 Years Frank Wilczek March 27, 2015.

3. K-clique y análisis sintáctico (parsing) en gramáticas libres de contexto.

Título. If the Current Clique Algorithms are Optimal, so is Valiant’s Parser

Abstract.

The CFG recognition problem is: given a context-free grammar G and a string w of length n, decide if w can be obtained from G. This is the most basic parsing question and is a core computer science problem. Valiant’s parser from 1975 solves the problem in O(n^{2.373}) time using fast matrix multiplication. Dozens of parsing algorithms have been proposed over the years, yet Valiant’s upper bound remains unbeaten. The best combinatorial algorithms have mildly subcubic O(n^3/\log^3{n}) complexity.  

Evidence for the nonexistence of efficient algorithms was given in a result of Lee (JACM’01), who showed that any algorithm for a more general parsing problem with running time O(|G| n^{3-eps}), that works even in the unusual case that |G|=Omega(n^6), can be converted into a surprising subcubic algorithm for Boolean Matrix Multiplication. However, nothing was known for the more relevant case of constant size grammars. 

In this work, we make the first progress on the constant size grammar case in 40 years, and prove that any improvement on Valiant’s algorithm, either in terms of runtime or by avoiding the inefficiencies of fast matrix multiplication, would imply a breakthrough algorithm for the k-Clique problem: given a graph of n nodes, decide if there are k that form a clique. 

Besides classifying the complexity of a fundamental problem, our reduction has led us to similar lower bounds for more modern and well-studied cubic time problems for which faster algorithms are highly desirable in practice: RNA Folding, a central problem in computational biology, and Dyck Language Edit Distance, answering an open question of Saha (FOCS’14).

4. Grafos como modelos.

Graphs are used as models in all areas of computer science: examples are state space graphs, control flow graphs, syntax graphs, UML-type models of all kinds, network layouts, social networks, dependency graphs, and so forth. Used to model a particular phenomenon or process, graphs are then typically analysed to find out properties of the modelled subject, or transformed to construct other types of models.

——————————————————————–

Nota.

A partir de aquí varios puntos sobre la Jerarquía Polinómica (PH). Cuando este blog era de investigación (hace ya más de cuatro años) hicimos una entrada sobre este tema que voy a releer ahora mismo (es la última entrada de una serie de varias que tratan sobre el mismo tema; se puede acceder a las otras desde la enlazada). En la entrada intentábamos relacionar la propiedad cycle- entangled que pensábamos se daba en los infinitos casos de Digrafos de Cayley bigenerados de los grupos PSL(t,2) (la t se refiere al orden la matriz y 2 se refiere al cuerpo finito de orden 2 o GF2, es decir las entradas de la matriz son binarias, 0 y 1), que tienen orden cercano a n^log2n con la PH. De momento no entiendo bien como intentaba (yo mismo) vincular estos conceptos, pero entiendo que tenía que ver con la propiedad de plegamiento de los digrafos de cayley cicle-entangled; si al plegarse se obtienen digrafos de tamaño menor y diferente a medida que n crece, el tiempo de verificación podría variar. Pero si el problema RH en los infinitos PSL(t,2) se relacionan de alguna manera con la PH, entiendo que se tiene que poder relacionar también con QSATk y no  veo la relación, aunque no es imposible  que exista: en esta otra entrada ya vimos como reducir el problema RH al problema SAT (en formulación DNF).  Casualmente en este artículo (The Complexity of Problems for Quantified Constraints. 2007) comentan que Completeness results are a form of lower bounds, and a question arising here is how much we can restrict our problems and still remain complete for important complexity classes. As an example, completeness of QSAT for PSPACE still holds if we restrict the formulas to 3-CNF (formulas in conjunctive normal form with at most 3 literals per clause) [SM73]. The problem QSATk remains complete for ΣkP if we restrict the formulas to 3-CNF for odd values of k, and to 3-DNF (formulas in disjunctive normal form with at most 3 literals per conjunct) for even k, as shown by Wrathall [Wra77]. El artículo citado es de C. Wrathall: Complete sets and the polynomial hierarchy.  El resultado comentado es el corolario 6.  Con todo esto no estoy diciendo que esta sea una linea a explorar…Tendría que volver a estudiar el tema en profundidad. Realmente cuanto más pienso sobre el tema  menos claro tengo que este problema pueda situarse en infinitos niveles de la PH y pueda relacionarse con QSATk.

En fin volviendo al tema que nos ocupa, tras la lectura, veo que ya teníamos las mismas dudas sobre la PH que seguimos teniendo ahora: mi capacidad para entender esta jerarquía no ha avanzado nada.

La advertencia que hacíamos para esa entrada se aplica a los siguientes puntos (sobre todo a las actualizaciones). Ahora con más razón pues tras dejar de estudiar estos temas cada vez nos cuesta más comprender la literatura…Y reconozco que nunca he tenido una idea completamente nítida del concepto de jerarquía computacional.

Fin de nota.

5. PH1. La jerarquía polínomica (PH) es infinita bajo oráculos aleatorios.

Comenzamos con una recomendación de lectura. Normalmente el concepto de jerarquía polinómica se presenta de manera muy abstracta e incomprensible para el lego. Para los interesados en conocer el alcance de este muy reciente resultado que comentamos en este punto se recomienda leer este artículo donde se presentan las diferentes formulaciones alternativas del concepto de PH de manera mucho más intuitiva y clara de lo que es habitual (pese a su claridad yo sigo teniendo una importante duda sobre la que hablaremos más adelante).

Explican para que tipos de problemas las clases NP y co-NP no son suficientes y que justifican la creación de la clase PH.

En cuanto al resultado se sabía que existían oráculos que hacían la jerarquía infinita. Ahora, con este reciente resultado, se sabe que esta es infinita en el caso medio, es decir ante un oráculo seleccionado aleatoriamente.

Extractos.

Meyer’s Question. Is there a relativized world within which the polynomial hierarchy is infinite? 

As discussed in the introduction (see Theorem 4), Hastad gave the first proof of a near-optimal n versus exp(n Ω(1/d) ) separation for the Sipser functions [H˚as86a], obtaining a strong depth hierarchy theorem for small-depth circuits and answering Meyer’s question in the affirmative.

… 

Given Hastad’s result, a natural goal is to complete our understanding of Meyer’s question by showing that the polynomial hierarchy is not just infinite with respect to some oracle, but in fact with respect to almost all oracles. Indeed, in [H˚as86a, H˚as86b, H˚as89], H˚astad poses the problem of extending his result to show this as an open question:

Question 1 (Meyer’s Question for Random Oracles [Has86a, Has86b, Has89]). Is the polynomial hierarchy infinite relative to a random oracle? 

Question 1 also appears as the main open problem in [Cai86, Bab87]; as mentioned above, an affirmative answer to Question 1 would imply Cai and Babai’s result showing that PSPACEA 6= PHA relative to a random oracle A. 

Cada vez me cuesta más leer sobre estos temas y tampoco estoy seguro que nunca comprendiese bien la relevancia de la idea de oráculo.  ¿ Significa esto que la jerarquia polínomica es infinita ?

Extracto

Further motivation for studying Question 1 comes from a surprising result of Book, who proved that the unrelativized polynomial hierarchy collapses if it collapses relative to a random oracle [Boo94].

El artículo de Book.

Abstract. If for almost every language A, the polynomial-time hierarchy relative to A collapses, then the (unrelativized) polynomial-time hierarchy collapses.

Es decir si colapsa en el caso medio, entonces colapsa en cualquier caso. Pero ¿ significa esto que si es infinita en el caso medio lo es en cualquier caso ?.

En el blog Computational Complexity comentan sobre este resultado.

Extracto.

In 1994, Ron Book showed that if the polynomial-time hierarchy was infinite that it remained infinite relativized to a random oracle. Rossman et al. thus gives even more evidence to believe that the hierarchy is indeed infinite, in the sense that if they had proven the opposite result than the hierarchy would have collapsed.

Luego el nuevo resultado no demuestra que sea infinita en cualquier caso.

En la página 6 hay una tabla muy interesante dónde muestran el progreso para las cuestiones PH^A !=PSPACE^A (desde 1986 ya se sabía que este resultado era cierto para el caso medio) y para la jerarquia polinomica (desde abril 2015 ya se sabe que es infinita para el caso medio oracular).

Aunque este nuevo resultado no demuestre que la PH es infinita en cualquier caso, ¿ la nueva evidencia inclina la balanza de manera definitiva hacía esta eventualidad ?

En este artículo de 1997, nos contestan de alguna manera:

 The Random Oracle Hypothesis is False. 1997.

The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the unrelativized case. Although this paper is not the rst to provide a counterexample to the Random Oracle Hypothesis, it does provide a most compelling counterexample by showing that for almost all oracles A, IP^A != PSPACE^A . If the Random Oracle Hypothesis were true, it would contradict Shamir’s result that IP = PSPACE. In fact, it is shown that for almost all oracles A, co-NP^A no está incluico en IP^A. These results extend to the multi-prover proof systems of Ben-Or, Goldwasser, Kilian and Wigderson. In addition, this paper shows that the Random Oracle Hypothesis is sensitive to small changes in the denition. A class IPP, similar to IP, is dened. Surprisingly, the IPP = PSPACE result holds for all oracle worlds.

Conclusiones. 

We have shown that random oracle results do not reliably predict the base case behavior of complexity classes. On the other hand, the meaning of random oracle results needs to be claried and remains an interesting problem. It would be very interesting to know if there are identiable problem classes for which the random oracle results do point in the right direction.

In addition, we would like to note that the IP = PSPACE and MIP = NEXP results demonstrated equality in the base case. In many other problems with contradictory relativizations, we expect the unrelativized complexity classes to be different (e.g., we expect that P != NP != PSPACE, etc). The next big challenge for complexity theorists is to resolve one of these problems. 

6. PH2. ¿ Que relación tiene el resultado anterior con jerarquías de nivel superior ?

Como el lector sabe me interesaron (y nos siguen interesando desde la distancia) mucho las clases EXP, NEXP y otras de este nivel, como la jerarquía exponencial. No se ahora mismo cuan relevante es este resultado, incluso si llegase a demostrarse que lo es en cualquier caso, para estas clases superiores.

We have ENE ⊆ EH ⊆ ESPACE,

EXPNEXP ⊆ EXPH ⊆ EXPSPACE, and

EH ⊆ EXPH.

7. PH 3. Un artículo de corte histórico que presenta el trabajo de Larry Stockmeyer, uno de los descubridores del concepto de PH. 

El artículo es de un bloguero experto en complejidad computacional (es uno de los dos editores del blog Computational Complexity, además de académico). En él comentan sobre dos problemas completos para los niveles 2 y 3:

–Nivel 2, succint set cover.

–Nivel 3, (succint) VC dimension. Ver actualización 3.

8. PH 4. Compendio de problemas en los niveles 2 y 3, à la Garey & Johnson. 

Título. Completeness in the polynomial hierarchy. A compendium, Schaefer, Uman. Versión 2001:Sigact, complexity column. Hay una versión de 2008.

Título. Completeness in the polynomial hierarchy. Part II. Schaefer, Uman. Sigact complexity column 38. 2002. Interesantes comentarios sobre problemas  sucintos.

Título. Completeness in the Delta (p,2) hierarchy. A compendium. Batzold, Morin y Pecoraro. 2009.

Título. Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy. Ronald de Haan, Stefan Szeider. 2014.

Tras hojear todos los artículos comentados en este y anteriores puntos, todo queda a un nivel demasiado abstracto. Mi gran duda ahora mismo es sobre que diferencia en complejidad temporal (expresada no es abstracto sino con funciones concretas) puede haber entre niveles de la PH (para más explicaciones sobre a que me refiero ver actualizaciones).  Si aceptásemos la Exponential Time Hypothesis (ETH)  la función correspondiente al nivel 1 sería 2^n. ¿ Que función se correspondería con el nivel 2, bajo la ETH ?.  ¿ Y si la ETH fuese falsa ?.  Ver actualizaciones para comprender porque tacho esta frase. Seguro que esta gran duda es evidente, pues nadie habla sobre ello….Si consigo aclararla actualizaré.

Actualización, un par de horas más tarde.

Si comprendí bien el concepto de Jerarquía exponencial cuando pasamos en ésta de nivel a nivel añadimos un nivel a la torre de exponentes.

En el caso de la jerarquía polínomica, como su propio nombre indica, añadiríamos un grado o una fracción de grado al polinomio del exponente ?

Si esta interpretación es correcta, a estos efectos la ETH es irrelevante.

Actualización 2. Mismo día. Este tema está cada vez más confuso. Según la definición habitual, cuando la clase de funciones:

–es p(n), con p un polinomio, se obtiene la PH.

–es 2^(log^c)* n, con c una constante, se obtiene la PLH (jerarquía polilogarítmica).

–es 2^cn, con c una constante, se obtiene la EH (jerarquía exponencial).

–es 2^p(n), con p un polinomio se obtiene la EXPH (jerarquía exponencial fuerte).

Luego la jerarquía exponencial no está basada en torres de exponentes. La clase correspondiente a torres de exponentes es ELEMENTARY.

Actualización 3, día siguiente. 

En este artículo comentan sobre las cotas superiores para el problema VC dimension (que no conocía y no comprendo muy bien; en esta presentación lo explican de alguna manera más detallada). La versión “normal” (el input representado por una matriz de incidencias) tiene complejidad temporal de decisión O(n^logn). Sobre la versión sucinta (representación del input mediante un circuito sucinto) informan que está en el nivel 3 de PH pero no dan cota superior. Recordemos que los Digrafos de Cayley 2-generados también tienen una representación sucinta (mediante dos permutaciones, el tamaño sería el grado de las permutaciones) o una representación normal, mediante la matriz de incidencias del digrafo. La diferencia entre ambas representaciones puede ser factorial.

Actualización 4. Idem.

Leyendo el artículo que escribí en su momento sobre la PH caigo en la cuenta que, en principio y si no estoy equivocado de nuevo, realmente el tiempo de decisión puede ser el mismo en todos los niveles de la PH e igual a NP, y lo que variaría sería el tiempo de verificación de la solución. ¿ Es correcto esto ?.

Actualización 5, 26 de abril 2015.

Por fin encuentro un artículo con cotas superiores algorítmicas para el problema QSAT (bastante reciente, aunque no tiene fecha seguramente de 2014):  Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity.

Extractos. 

Moreover, in theory, comparatively very little is known concerning general worst-case algorithms for QBF. 

Theorem 1.2 and Theorem 1.3 together show that the “hard” cases of satisfiability of quantified Boolean formulas are where the number of quantifier blocks is between Θ(log(n)/ log log(n)) and Θ(log(n)) – in all other cases, we are able to obtain non-trivial savings.

De uno de los dos autores: Ironic complicity: satisfiability algorithms and circuit lower bounds. 2013.

Abstract. I discuss recent progress in developing and exploiting connections between SAT algorithms and circuit lower bounds. The centrepiece of the article is Williams’ proof that NEXP * ACC 0 , which proceeds via a new algorithm for ACC 0 -SAT beating brute-force search. His result exploits a formal connection from non-trivial SAT algorithms to circuit lower bounds. I also discuss various connections in the reverse direction, which have led to improved algorithms for k-SAT, Formula-SAT and AC 0 -SAT, among other problems.

Una presentación con más algoritmos.

Todavía no tengo claro que entienda bien el problema QSAT. Si te pasa lo mismo puedes leer esta presentación:

Extracto. 

(1,2)-QSAT

A (1,2)-QCNF-formula is a closed quantified formula of the following type

∀X∃Y ϕ(X,Y)

–X and Y denote distinct sets of variables,

–ϕ(X,Y) is a 3-CNF-formula such that each clause contains exactly 1 variable from X and exactly 2 variables from Y.

–(1,2)-QSAT the property for an (1,2)-QCNF-formula of being true.

An example for a (1,2)-QCNF-formula

Let X = {x1, x2} and Y = {y1, y2, y3}

∀x1∀x2∃ y1∃ y2∃ y3 (x1y¯1y2) ∧ (x¯2y2y3) ∧ (x¯1y¯1y¯3)

Entiendo que lo anterior significa que “para toda asignación de valores a x1 y x2, existe una asignación de valores para y1, y2 e y3 que satisface la fórmula”. Y entiendo que el algoritmo evidente de fuerza bruta asigna valores a todas las combinaciones posibles de variables universales y para cada combinación encuentra una asignación a las variables existenciales que satisfaga la  formula. En este caso como hay dos variables universales, hay 4 combinaciones posibles, que se deben de verificar. Aparentemente esta lectura no es correcta. Se debe de leer: “para toda asignación de valores verdaderos de las variables universales (For every (truth assignement of) x1 and x2), existe alguna asignación  de valores  a las variables existenciales (there exists some truth assignement of)”. Todavía no tengo muy claro esto, que es clave. También puede haber variables no  cuantificadas a las que se llama variables libres (a las cuantificadas se les llama ligadas).

Esta otra presentación me hace volver a la lectura original.

Extracto.

Example: φ = (x1 o  x2  o no x3 ) y ( no x2 o no x3 ) x1 x2 x3 φ?

Existe1, Univx2, Existex3  φ ?

YES: x1=T; if x2=T, set x3=F; if x2=F, set x3=T.

Por otra parte entiendo que a toda formula QSAT se le puede hacer corresponder una fórmula SAT (no cuantificada) equivalente de mayor tamaño (con mismo número de variables pero más cláusulas). Si esto es correcto, y el numero de variables universales es grande (cercano al numero de variables), el tamaño de la formula SAT con repecto a la original QSAT podría incrementarse exponencialmente. De alguna manera QSAT es una manera sucinta de representar SAT. Confirmo (gracias al último enlace señalado) que es correcto: a la transformación mediante la cual se pasa de QSAT a SAT se la llama eliminación de cuantificadores. y todas las variables quedan libres. También confirmo, gracias al mismo enlace, que al pasar de una QSAT de tamaño n con k variables cuantificadas  a una SAT con todas las variables libres el tamaño puede ser O(2^n*k).  En el mismo enlace utilizan la palabra sucinta. Nunca un enlace había aclarado tantas dudas y de manera tan seguida…:-).

Un artículo con cotas superiores para variaciones de SAT. Hablan de la ETH.

Me interesa sobre todo el tiempo de verificación y como son las diferencias entre niveles de la PH. Esto era la pregunta original y no hemos avanzado nada. ¿ O si ?. En este artículo (Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy) hablan de la jerarquía polilog que para NEXP cumple el mismo papel que la PH para E: In essence the PL-hierarchy plays the same role for the EXP-hierarchy as the polynomial hierarchy does for the E-hierarchy. Esto puede ser muy informativo. Más mañana.

Fin de actualización.

———————————————————————

9. Un libro clásico, el clásico, sobre complejidad computacional: Computers and Intractability. A guide to the theory of NP-completeness. 

Para aquellos que no conozcan la teoría de la complejidad computacional, les sorprenderá ver los compendios citados en el punto anterior. Es un formato muy útil de presentación de problemas que creo se inició en este libro que aunque se publicó en 1979, sigue de plena actualidad.

Al margen del contenido, para mi sólo el formato de presentación de los problemas en el compendio (que no se  si es original de este libro o ya existía antes) ya es todo un hallazgo. Ahora mismo no recuerdo si en el libro de G&J los incluían o no (en los compendios anteriores y otros que existen accesibles en internet), pero hecho de menos en la sección comentarios la mejor cota superior disponible para cada problema, el mejor algoritmo con expresiones de complejidad con constantes. Esto entiendo que es más relevante para los problemas en la PH que para los problemas NP-completos.

El primer capítulo en PDF.

10. Artículo. A Brief History of NP-Completeness, 1954–2012 David S. Johnson. 2012.

Johnson es uno de los dos autores del libro citado en el punto anterior. La fecha de 1954 puede sorprender. La explicación es clara: incluyen la famosa correspondencia entre Godel y Von Neumann, que además ha dado título e identidad a uno de los blogs punteros sobre complejidad computacional.

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: