¿Relación entre simetría e intratabilidad computacional?

El problema de automorfismo libre de puntos con punto fijo solicita un automorfismo gráfico que mueva al menos k ( n ) nodos. El problema es N P -completo si k ( n ) = n c para cualquier c > 0.$k$$k(n)$$NP$$k(n)=n^c$$c$

Sin embargo, si entonces el problema es el tiempo polinómico Turing reducible al problema de isomorfismo gráfico. Si k ( n ) = O ( log n / log log n ), entonces el problema es el tiempo polinómico equivalente a Turing al problema del Automorfismo de gráficos que está en N P I y no se sabe que es N P- completo. El problema del automatismo gráfico es Turing reducible al problema del isomorfismo gráfico.$k(n)=O(\log n)$$k(n)=O(\log n/\log \log n)$$NPI$$NP$

Sobre la complejidad de contar el número de vértices movidos por los automatismos de gráficos, Antoni Lozano y Vijay Raghavan Foundation of Software Technology, LNCS 1530, pp. 295–306

Parece que la dureza computacional aumenta a medida que aumentamos la simetría del objeto que estamos tratando de encontrar (como lo indica la cantidad de nodos que el automorfismo debe mover). Parece que esto puede explicar la falta de tiempo polinomial Reducción de Turing de la versión NP completa a Graph Automorphism (GA)

¿Hay otro ejemplo de un problema difícil que respalde esta relación entre simetría y dureza?

Esta no es exactamente la "misma" relación entre simetría y dureza, pero existe una estrecha relación entre las simetrías de una función booleana y su complejidad de circuito. Ver:

Babai, L., Beals, R. y Takácsi-Nagy, P. Simetría y complejidad , STOC 1992.

Esto es lo que muestran. Sea una secuencia de grupos de permutación. Sea s ( G i ) el número de órbitas de G i en su acción inducida en { 0 , 1 } i (por permutación de las coordenadas). Supongamos que F ( G ) denota la clase de lenguajes L de modo que L ∩ { 0 , 1 } n es invariante bajo G n . Entonces todos los idiomas en $G_{i} \leq S_{i}$$s(G_{i})$$G_{i}$$\{0,1\}^{i}$$\mathcal{F}(G)$$L$$L \cap \{0,1\}^{n}$$G_{n}$ tienen circuitos de tamaño como máximo p o l y ( s ( G ) ) y profundidad como máximo p o l y ( log ( s ( G ) ) , y esto es esencialmente estricto.$\mathcal{F}(G)$$poly(s(G))$$poly(\log(s(G))$

En la dirección opuesta, varios problemas cuyos conjuntos de testigo tener porciones de simetrías terminan siendo en c o A M (como G I ), y así no son N P -Complete a menos que P H colapsa. De hecho, el siguiente documento muestra que los problemas de N P cuyos conjuntos de testigos tienen muchas simetrías son bajos para P P :$NP$$coAM$$GI$$NP$$PH$$NP$$PP$

Arvind, V., Vinodchandran, NV La complejidad de contar de los lenguajes definibles en grupo . Theoret Comput Sci. 242 (2000), no. 1-2, 199--218.

$PP$$NP$$PP^{PH} \subseteq BP \cdot PP$$BP \cdot PP = PP$$NP$$PP$$PP$$NP$$NP$$PP$

$f$$f(x) = f(y)$$x \sim y$$NP$

Finalmente, el programa de la teoría de la complejidad geométrica de Mulmuley-Sohoni se trata esencialmente de utilizar la simetría para demostrar la dureza, aunque la conexión simetría-dureza allí es más sutil y menos directa.

Las instancias SAT estructuradas, que exhiben muchas simetrías, parecen más fáciles de resolver que las instancias SAT aleatorias. Codificar problemas del mundo real en SAT siempre da lugar a instancias estructuradas (lo cual no es sorprendente, ya que los problemas del mundo real que enfrentamos tienen simetrías). Los mejores solucionadores SAT completos pueden resolver de manera eficiente instancias del mundo real con hasta 1,000,000 de variables, pero ninguna de ellas, hasta donde yo sé, es capaz de resolver de manera eficiente instancias aleatorias con, digamos, 10,000 variables (en Edward A. Hirsch página de inicio es posible encontrar algunos casos sorprendentemente pequeñas azar, contra la que incluso los mejores solucionadores SAT completos consiguen stucked). Así, desde un punto de vista empírico, la presencia de simetrías parece disminuir la dureza.