PH (actualizado 27 y 28 de noviembre).

Advertencia: este es un post sobre una investigación en curso. Puede contener información y incorrecta y los contenidos están sujetos a modificación.

En lo que sigue proseguimos la investigación intentando obtener una visión general de las clases de complejidad teniendo en cuenta el resultado principal al que hemos llegado (una cota superior para la clase de complejidad Pspace-complete), que incluya a las clases de complejidad PH y NP.

En concreto nos preguntamos ¿ que propiedad hace diferentes a los Digrafos de Cayley bigenerados que están en la clase Pspace-completos, de los que están en la clase PH y en la clase NP-Completos ? y contestar a la pregunta con una posibilidad, cuya validez debemos  determinar: esta propiedad es la de ser cycle-entangled. Esto nos lleva primero a conocer mejor la clase PH (que conociamos muy superficialmente), a estudiar cómo encajar las diferentes caracterizaciones de esta clase PH con la propiedad cycle-entangled y a preguntarnos si la familia infinita de grupos grupo PSL(t,2) es suficientemente rica para expresar todas estas clases y si hay otras familias infinitas de grupos de orden cuasipolinómico para cada grado. Cómo siempre este es un post dinámico, al que iré añadiendo y del que iré eliminando información (incorrecta) según vaya avanzando . En todo lo que sigue cuando digo grupo me refiero a grupo bigenerable, excepto cuando se especifique lo contrario.  Un resumen sobre cómo veo el tema en la última actualización del día 28/11/2010 con una lista de los posibles problemas asociados a esta interpretación (que no son pocos).

1. Sobre la propiedad cycle entangled:

He revisando mi base de datos de Digrafos de Cayley cycle-entangled. Algunos ejemplos de este tipo de digrafos de grupos de orden pequeño (24):

–caso  1: identidad 23456789, generadores 47395268 y 23564897. Permutaciones de grado 8, se genera un grupo  de orden 24, un generador es de orden 3 (y por lo tanto no puede ser cycle-entangled ya que solo  pueden ser cycle-entangled los ciclos de orden no primo par), el otro es de orden 4 y es cycle entangled (incluye 2 arcos de 2 diferentes IAS) y el IAS es de orden 12, es decir contiene 12 permutaciones diferentes y hay cuatro IAS. En general la mitad del orden del IAS, es decir |IAS|/2 divide al orden del grupo. Cada dos IAS están entrelazados 4 veces es decir si consideramos el IAS un conjunto de permutaciones, contienen 4 permutaciones comunes. Hay 6 ciclos de orden 4 (en general el orden del ciclo divide al orden del grupo) y cada uno incluye arcos de un par de IAS.

–caso 2: identidad 23456789, generadores 32567894 y 47683952. Permutaciones de grado 8, se genera un grupo de orden 24. Los dos generadores son de orden 6 y los dos ciclos son cycle-entangled. El IAS es de orden 8, y por lo tanto hay 6 IAS diferentes y cada ciclo incluye arcos de 3 IAS diferentes. Este digrafo, que no solo es vertice-transitivo sino también arco-transitivo y por lo tanto mucho más simetrico, se puede reducir a uno de orden 12 con ciclos de orden 3. Se resuelve el problema RH en este digrafo reducido y luego se recupera el digrafo original, y RH del reducido se transforma en un RH del original, aunque si es un path pueda cambiar el vertice final

–caso 3: identidad 123456, generadores 214536 y 123564. Permutaciones de grado 6, se genera un grupo de orden 24. Un generador es de orden 3 y el otro de orden 6. El de orden 6 es cycle-entangled apareciendo arcos de 3 IAS diferentes. Los IAS son de orden 12 y por lo tanto hay 4 IAS.

–caso 4: este lo describo de manera más abstracta. Orden del grupo 24, un generador involución (de orden 2) y un generador de orden 6. El de orden 6 cycle-entangled, con arcos de 3 IAS. Cada IAS tiene es de orden 12, y por lo tanto el digrafo tiene 4 IAS diferentes. Este digrafo se reduce a un digrafo de 12 vertices, de 4 ciclos de orden 3.

Esta simple muestra ya indica la variedad que puede haber dentro de los digrafos cycle-entangled y el parámetro más relevante: cuantos arcos de un mismo IAS se incluyen en un mimo ciclo, parámetro al que podemos llamar divisor. El divisor es importante ya que al reducir un digrafo a otro similar de tamaño inferior, lo dividimos por el divisor de los dos ciclos. Al final, entiendo que se reduce a ciclos de orden primo (indemostrado). La operación de reducción es más bien una operación de plegamiento: arcos y vertices que están separados en el digrafo original se identifican en el reducido.

Otro tema importante indemostrado es si, en general, el digrafo al que se reduce el digrafo original es también un digrafo de Cayley: está claro que es un digrafo similar, vertice transitivo, con IAS, al que se pueden aplicar todos los métodos que hemos descrito en la patente y que estamos describiendo en el blog, que no dependen de que el digrafo sea un digrafo de Cayley, si no de que se pueda descomponer en IAS. Esto puede ser importante, ya que si no fuesen digrafos de Cayley, no se les puede aplicar teoremas solo válidos para digrafos de Cayley y también porque las propiedades de estos podrian ser diferentes a las de los Digrafos de Cayley y las subrutinas que hemos visto pueden valer para casos difíciles de Digrafos de Cayley (ver post anterior) que se basan en estas propiedades, podrían no ser validas en estos digrafos reducidos. También es un tema importante, pendiente de aclarar, el saber si diferentes digrafos originales se pueden reducir a un mismo digrafo reducido.

Dados dos generadores de grado n cómo input, lo primero que hay que hacer es determinar si son cycle-entangled y en que medida lo son, es decir obtener el  valor del divisor. El coste computacional en tiempo de estas operaciones variará dependiendo del orden del IAS y del orden de los generadores (de los ciclos). Todavia no tengo claro cual sería la manera más eficiente de hacer esto cuando el input es sucinto. El tamaño máximo del IAS o del ciclo es n^log2n. En principio varios IAS de tamaño (n^log2n)/x podrian constituir un digrafo de orden n^log2n. Si los 2 ciclos son cycle-entangled tal que cada ciclo tiene x arcos del mismo IAS, al reducirlo se obtendria un digrafo de tamaño n^log2n/y. Posiblemente x e y no sean independientes y estén ligados de alguna manera que de momento desconozco. Un primer paso es expresarlos en terminos del grado n.

Cada vez parece más clara una cosa: en el núcleo de los problemas más complicados de resolver, parecen encontrarse los casos cycle-entangled y dentro de estos, deben estar los problemas NP-completos. Es decir estos parecen representan la complejidad en su estado más puro

Actualización 27/11/2010.

a) Ahora desarrollo con más detalle la idea sobre la propiedad cycle entangled y PH. Me limito a analizar el caso para PSL(t,2), aunque cómo desarrollo en el punto 4 de éste mismo post pueda haber otras familias infinitas de grupos de orden cuasipolinómico para los cuales se pueda aplicar el mismo argumento o esquema. Para cada grado n, hay un grupo PSL (t,2) de orden cercano a m=n^log2n. Los pares de generadores no isomorfos de este grupo pueden tener IAS de diferente tamaño (número de permutaciones que se generan desde la unidad hasta llegar de nuevo a la unidad). En principio puede haber IAS de tamaño igual al orden del grupo, de la mitad, de un tercio de un cuarto…es decir de tamaño m/d1, m/d2, m/d3….siempre y cuando dn divida a m. Pero entiendo que puede haber casos en que dn divida a m pero no haya IAS de ese tamaño. A medida que el entero m/dn es más pequeño el digrafo está menos entangled (empieza siendo cycle-entangled, luego sólo entangled) hasta que llega un momento en que debido al reducido tamaño del IAS si fuese entangled y no podría obtener un grupo de ese orden.

Primer dato: para todo n hay una franja de casos difíciles.

La dificultad del test para averiguar si el caso es cycle-entangled, y si lo fuese, calcular el divisor depende obviamente del tamaño del IAS, cuanto más grande más tiempo.

–Segundo dato: la franja de dificultad se divide en grados (medidos en diferencia de tiempo). Duda: puede un caso con IAS de tamaño m/2 ocupar un escalón diferente de la PH que uno de tamaño m/3 ?

Por otra parte cuanto mayor es n, mayores divisores tendrá el grupo y es posible (duda) que la franja de dificultad sea cada vez más y más ancha (incluya más casos). Si a medida que n crece, la franja de dificultad tiene cada vez más diferencias de grado y cada diferencia de grado (o una serie de diferencias de grado) de la franja de dificultad se corresponde con escalones de la PH, entonces la cota superior obtenida es compatible con “el estado de las conjeturas” de una PH infinita.

b) Supongamos que las operaciones de identificación de un caso cycle-entangled, del computo del divisor y de reducción se pueden decidir y verificar hacer en espacio polinómico, entonces los casos más dificiles cycle-entangled de la franja de dificultad, se pueden reducir a casos más fáciles sin salir de Pspace. No a casos más fáciles del mismo orden sino a casos más fáciles de orden diferente, inferior (recordemos que el orden del caso se divide por el número que se obtiene al multiplicar los divisores (primos entre ellos) aunque quizás todavia de orden cuasipolinómico. Entonces un caso de dificultad superiors o se reduce a PH o a NP o se quedan en PH con menor nivel de dificultad ( ¿ pero en un escalón diferente ?).

Exploremos primero la posibilidad de que se reduzcan a NP. Para que la propiedad cycle-entangled pueda explicar la diferencia entre los casos Pspace y los casos NP, que es la tesis que estamos manteniendo en este post, tiene que haber casos dentro de la franja difícil, casos cycle-entangled que se puedan  reducir a casos dónde todos los parámetros relevantes sean polinómicos con respecto al grado n de las permutaciones original. ¿ es esto posible ? Esto es la clave. Esto en principio depende de tres parámetros: orden o tamaño del IAS, orden de los generadores y divisor. Dado un orden, cuanto mayor sea el ciclo de los generadores y mayor el divisor (lo cual implica un IAS grande) mayor será el salto que genere la reducción. Pero puede haber un salto de n^log2n a p(n), con p() polinomio que se mantenga asíntoticamente ?  Aquí también hay que tener en cuenta el grado del polinomio. Para los problemas en P el grado puede ser cualquiera pero se exige que sea constante. Entonces hay un grado tal que para todo n haya casos cycle-entangled que se puedan reducir para todo n o al menos paraun numero infinito de n´s a tamaños de un polinomio de ese grado ?

actualización 28 noviembre 2010.

A continuación resumo cómo veo ahora el tema.

Para cada n y cada grupo hay cómo cuatro fases: cycle-entangled con o sin RH reducibles, fase entangled en los que los casos no tienen RH, fase entangled en los que si hay RH pero puede haber obstáculos y fase fáciles.

En general se acepta la conjetura que Pspace-complete es diferente de PH y PH diferente a NP. Si fuese igual la PH a alguna de estas clases colapsaria. Entonces una posible intepretación de las cuatro fases de los grupos PSL(t,2) es: fase cycle-entangled con RH o sin RH reducibles nos darian casos de las clases PH o NP-completos o Co-Np-completos dependiendo del tamaño/orden de los parámetros del caso reducido (confirmo que experimentalmente existen casos cycle-entangled sin RH); fases entangled sin RH y entangled con obstáculos nos darian los casos de complejidad Pspace-complete (que cómo se sabe es igual a co-Pspace-complete); fase fácil = P. Otros posibles grupos de orden cuasipolinómicos (n^log3n, n^log4n….), además de los reducidos  serían los que ocuparian los diferentes niveles de la PH. Cuando añadimos grupos que necesitan más de dos generadores entonces ya aparecen otras clases de complejidad más elevevada (EXP…) y quizás añadamos también densidad.

Problemas con con esta interpretación.

–Problema de reducción: ¿existen casos cycle-entangled que se reducen a NP? Ver último párrafo de “actualización 27/11/2010”. Hay que demostrar que esta reducción existe y que se puede hacer con los recursos de Pspace.

— Problema de teoria de grupos: ¿ existen otros grupos de orden cuasipolinómico ? ver punto 4 de este post.

–Problema de densidad: Sabemos que las clases que contienen problemas completos no pueden ser sparse.

Problema de infinitud de PH (no colapso): ¿ obtenemos una PH con un numero infinito de “escalones” de esta manera ?

2. Sobre la clase PH:

Al caracterizar NP todos los autores comentan que comprende la clase de problemas que se puede verificar en tiempo determinista polinómico pero no tengo claro si esta caracterización se extiende a la PH, ya que los problemas incluidos en sus diferentes niveles no se pueden verificar en tiempo determinista polinómico pero entiendo que si se pueden verificar en tiempos deterministas superpolinómicos cada vez mayores, a medida que subimos en la jerarquía, tal y cómo aparece reflejado en la tabla siguiente que he preparado para explicar mejor las dudas que tengo sobre la clase PH (los datos que aparecen en la tabla son cotas superiores o inferiores conocidas (en azul claro) o supuestas (el resto); en rojo las cotas superiores que no tengo claras ni siquiera cómo supuestos). Quizás alguien eche de menos en la tabla, con razón, los complementarios (Co-NP etc…):

Computación o decisión Solución Verificación Solución
Tiempo Espacio Tiempo Espacio
PSPACE N^log2n P n^log2n P
PH ¿N^log2n en sus infinitos niveles? P  ¿n^log3n, n^log4n…? P
NP N^log2n P P P
P Polinómica =P P P P

Ya he empezado a leer algo sobre ésta clase y a continuación resumo lo que he asimilado. La jerarquia polinómica de tiempo se definió en este paper “The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space” por A. Meyer and L. Stockmeyer en 1972. La PH se puede caracterizar de varias maneras alternativas pero equivalentes: máquinas de Turing alternadas, máquinas de Turing oraculares, en terminos de teoria de juegos o Pruebas Interactivas. Sabemos que el problema canónico NP-completo es SAT, el problema canónico PSPACE-completo es QSAT (también llamado TQBF: http://en.wikipedia.org/wiki/True_quantified_Boolean_formula), es decir SAT con las variables cuantificadas con cuantificadores existenciales y universales. El problema canónico es dentro de la jerarquia es QSATk, dónde k expresa el numero de veces que se alternan los cuantificadores de las variables en las formulas. Un paper de Stockmeyer sobre PH: http://www.oocities.com/stockmeyer@sbcglobal.net/pth.pdf  y un libro dónde se explica muy claramente, y gráficamente todo ésto (ver capítulo 2). La caracterización de la PH mediante pruebas interactivas (Interactive Proofs) sí que habla de tiempo de verificación, pero no determinista, tampoco no-determinista, sino probabilista. De momento no sé si esto nos sirve para aclarar las dudas pendientesA continuación anoto algunas consecuencias de complejidad computacional relacionadas con PH, explicadas también muy claramente en el libro citado anteriormente.

Si P es igual a NP entonces P es igual a PH (por el colapso de la jerarquia). Pero si P no es igual a NP la jerarquia no es necesariamente infinita: se podría dar el caso de que colapasase a algún otro nivel (segundo nivel, tercer nivel…) y sería finita. Si se demostrase inclusión estricta entre un nivel y el siguiente entonces la inclusión sería estricta también para todos los niveles inferiores.

3. Sobre definiciones alternativas de la clase PH y la propiedad cycle-entangled:

Esta parte es de momento totalmente especulativa y seguramente totalmente errónea y por lo tanto la más dinámica del post.

Me pregunto también cómo encaja la caracterización de PH mediante alternación de cuantificadores, o cómo juegos, con la que nosotros estamos intentando construir. Una posibilidad para  expresar mediante alternación de cuantificadores (o cómo un juego) nuestro problema RH es la siguiente: cada variable es un IAS y cada  asignación de valor (un generador u otro) a una variable es una alternancia. Al marcar en el IAS inicial el vertice final se determina el juego que se va a jugar. En la primera opción empieza el jugador uno  marcando un IAS; luego el jugador 2 marca un IAS…así hasta que se obtiene un RH o no. Si el RH se obtiene cuando marca el jugador 1, gana el jugador 1. Si se obtiene cuando gana el jugador 2, gana el jugador 2. Se  darian tablas cuando se ha llegado a una situación en la que no es posible que ningún jugador obtenga un RH marcando ninguno de los IAS que quedan. Esta versión del juego todavia no me convence, parace demasiado libre: un jugador debe perder si entra en contradicción (si hace algún movimiento que haga imposible un RH) y quizás se deba exigir que  los jugadores solo puedan elegir en cada jugada asignar un IAS, aquel que continue el path. Por otra parte no veo claro porqué no se pueden expresar así también los problemas en NP.

Recordemos que según el algoritmo presentado en la solicitud de patente, cuando se han extraido todas las consecuencias necesarias de marcar un determinado IAS, se debe optar por activar un IAS por un generador u otro y hay varias opciones hasta obtener un RH (en algunos digrafos hay más opciones y en otros menos). Durante el juego cada jugador debe de ser capaz de calcular su mejor jugada independientemente de lo que haga el otro jugador(es decir teniendo en cuenta todas las posibles activaciones de su oponente) en la siguientese jugadas (esto es la alternancia de cuantificadores: para el jugador 1 se puede expresar ¿ existe una asignación de un valor a una variable, tal que para toda asignación que pueda hacer mi oponente a cualquier otra variable, existe una asignación de una variable que yo pueda hacer…así tantas veces cuantas variables haya). Entonces: dado un juego (un Digrafo de Cayley y un vertice final e inicial del IAS inicial marcado) ¿ ayudaría a ganar a un jugador, el poder conocer cuales son las opciones  (según hemos descrito anteriormente) que llevan a obtener un RH  para toda marcación inicial de cualquier IAS, si el otro no las conoce ?  Salvo en juegos con “soluciones únicas” en las que dado el vertice inicial y final solo hay un RH,  el número de opciones depende de las elecciones que vayan haciendo los jugadores; parece claro que la paridad del número de opciones es un dato clave para ganar. Posiblemente el jugador que pueda forzar la paridad que le convenga ganará. ¿ le ayuda a esto disponer de la información que hemos comentado antes?

Por otra parte cuanto más entrelazado está un caso (cómo es el caso de digrafos cycle-entangled) menos opciones hay. ¿Cómo podemos entonces relacionar la carácterización anterior con este hecho, si es que tiene algún sentido realizar ésto ?

Continuará…

Actualización 27 de noviembre 2010.

del artículo de wikipedia sobre PH: http://en.wikipedia.org/wiki/Polynomial_hierarchy.

“A complete problem for \Sigma_k^{\rm P} is satisfiability for quantified Boolean formulas with k alternations of quantifiers (abbreviated QBFk or QSATk). This is the version of the boolean satisfiability problem for \Sigma_k^{\rm P}. In this problem, we are given a Boolean formula f with variables partitioned into k sets X1, …, Xk. We have to determine if it is true that

 \exists X_1 \forall X_2 \exists X_3 \ldots f

That is, is there an assignment of values to variables in X1 such that, for all assignments of values in X2, there exists an assignment of values to variables in X3, … f is true? The variant above is complete for \Sigma_k^{\rm P}. The variant in which the first quantifier is “for all”, the second is “exists”, etc., is complete for \Pi_k^{\rm P}.”

Luego el “modelo” que estamos planteando en este punto no es equivalente a este. Debemos revisarlo.

4. ¿ Son suficientes los grupos PSL(t,2) ?:

Es decir además de los grupos PSL(t,2) ¿que otros grupos tienen un orden superior a polinómico e inferior a n^log2n ?
¿ Porqué esta pregunta ? Hemos concluido (estamos en el escenario) de una complejidad asintótica peor caso para un problema Pspace-completo es n^(log2n) y sabemos que al menos existe una clase infinita de grupos que se aproximan a esta cota superior asintóticamente (grupos PSL (t,2)); también  hemos identificado una propiedad de los Digrafos de Cayley (el ser “cycle- entangled”) que puede explicar que haya casos que cuya solución no se computar de manera eficiente pero una vez computada la solución, su correción se pueda computar de manera eficiente (es decir casos en NP), puedan . No tengo muy claro si los grupos PSL(t,2) son suficientemente densos (en numero de casos para cada grado) y ricos para expresar los casos más difíciles de todas estas clases. Puede haber, además de PSL(t,2) otras familias infinitas de grupos de orden entre la cota superior (n^(log2n)) y la complejidad polinómica, que llenen la jerarquia polinómica (PH). Es decir para cada grado podría haber grupos de, por ejemplo, orden n^(log3n), n^(log4n)…¿ existen estos grupos ?

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: