Representación sucinta de circuitos de gráficos

La clase de complejidad PPAD (por ejemplo, el cálculo de varios equilibrios de Nash) se puede definir como el conjunto de problemas de búsqueda total polytime reducible a FIN DE LA LÍNEA :

FIN DE LA LÍNEA : Dados los circuitos S y P con n bits de entrada y n bits de salida de modo que P (0 ⁿ ) = 0 ⁿ ! = S (0 ⁿ ) , encuentre una entrada x en {0,1} ⁿ tal que P (S (x)) ! = X o S (P (x)) ! = X ! = 0 ⁿ .

Los circuitos o algoritmos como S y P definen implícitamente un gráfico exponencialmente grande que solo se revela consulta por consulta (¡para mantener el problema en PSPACE !), Por ejemplo, el artículo de Papadimitrou .

Sin embargo, no entiendo cómo se diseñaría un circuito que permita gráficos arbitrarios (si hay una estructura sistemática en el gráfico, parece mucho más fácil encontrar el circuito). Por ejemplo, ¿cómo diseñaría un circuito de tamaño polinómico que represente una línea dirigida exponencialmente larga, con una etiqueta de todo 0 para el vértice fuente y etiquetas binarias asignadas aleatoriamente a todos los demás vértices? Esto parece estar implícito en los documentos relacionados con PPAD .

Lo más cerca que he llegado de una búsqueda en línea es el artículo de Galperin / Widgerson , pero el circuito descrito allí toma dos etiquetas de vértice y devuelve una respuesta booleana a "¿Son estos vértices adyacentes?"

Entonces, ¿cómo diseñaría un circuito de tamaño polinómico de un gráfico de tamaño exponencial que toma una entrada de n bits y emite la etiqueta de n bits de su predecesor o sucesor, respectivamente? O incluso, ¿alguien conoce un recurso que lo explique bien?

Su pregunta parece ser la siguiente: ¿cómo se representan gráficos arbitrarios (o incluso gráficos de ruta arbitrarios) como un circuito de tamaño polinómico? La respuesta es que no. El número de gráficos de ruta diferentes con 2 ⁿ vértices es (2 ⁿ ) !, mucho más que el número de circuitos diferentes con puertas n ^c (exponencial en n ^c log n). Por lo tanto, casi todos los gráficos con tantos vértices no pueden representarse mediante un circuito sucinto.

Por lo tanto, como insinúa, en cierto sentido solo los gráficos que tienen un alto grado de estructura se pueden representar de esta manera. Eso es lo que hace que las clases de complejidad como PPAD sean interesantes: a pesar de la estructura que sabemos que deben tener los gráficos de entrada para el problema EOL, no parecemos saber cómo aprovechar la estructura para resolver el problema de manera eficiente.

Si no estoy entendiendo su pregunta y realmente está preguntando: ¿cómo se hace un circuito que cumpla con los requisitos de entrada para EOL, incluso para un gráfico muy estructurado: pruebe el gráfico de ruta que conecta el vértice x (considerado como un número en binario) a x-1 y x + 1, con extremos en cero y en 2 ^ n-1. O si desea algo menos trivial que parece más difícil de resolver EOL: deje que E y D sean las funciones de cifrado y descifrado para una clave fija en su sistema criptográfico favorito, deje que los vecinos de x en el gráfico sean E (x) y D (x), y deje que los extremos de la línea sean 0 y D (0).

Como la mayoría de los gráficos en n vértices son aleatorios de Kolmogorov, no pueden ser descritos por un circuito (o cualquier otro programa) que sea significativamente más pequeño que el gráfico en sí. (Si no sabe lo que significa Kolmogorov-random, básicamente puede tomar la conclusión de la oración anterior como su definición. Luego confíe en el hecho de que casi todas las cadenas son Kolmogorov-random).

Aunque no estoy íntimamente familiarizado con los trabajos que citó, supongo que siempre están hablando de gráficos descritos por circuitos. En otras palabras, al enfocarse en los circuitos, esencialmente están restringiendo su atención a la clase de gráficos que tienen circuitos sucintos (cuyo tamaño es logarítmico en el tamaño del gráfico).