Relation entre symétrie et intraitabilité informatique?

Le problème de l'automorphisme libre à points fixes demande un automorphisme de graphe qui déplace au moins k ( n ) nœuds. Le problème est N P -complet si k ( n ) = n c pour tout $k$$k(n)$$NP$$k(n)=n^c$$c$ > 0.

Cependant, si alors le problème est le temps polynomial Turing réductible au problème d'isomorphisme graphique. Si k ( n ) = O ( log n / log log n ) alors le problème est le temps polynomial équivalent à Turing au problème de l'automorphisme graphique qui est dans N P I et n'est pas connu pour être N $k(n)=O(\log n)$$k(n)=O(\log n/\log \log n)$$NPI$$NP$ complet. Le problème de l'automorphisme graphique est Turing réductible au problème de l'isomorphisme graphique.

Sur la complexité du comptage du nombre de sommets déplacés par les automorphismes graphiques, Antoni Lozano et Vijay Raghavan Foundation of Software Technology, LNCS 1530, pp. 295–306

Il semble que la dureté de calcul augmente à mesure que nous augmentons la symétrie de l'objet que nous essayons de trouver (comme indiqué par le nombre de nœuds qui doivent être déplacés par l'automorphisme). Il semble que cela puisse expliquer le manque de réduction du temps polynomial de Turing de la version NP-complète à Graph Automorphism (GA)

Y a-t-il un autre exemple d'un problème difficile qui soutient cette relation entre la symétrie et la dureté?

Ce n'est pas exactement la "même" relation entre la symétrie et la dureté, mais il existe une relation étroite entre les symétries d'une fonction booléenne et sa complexité de circuit. Voir:

Babai, L., Beals, R., et Takácsi-Nagy, P. Symétrie et complexité , STOC 1992.

Voici ce qu'ils montrent. Soit une suite de groupes de permutation. Soit S ( G i ) le nombre d'orbites de G i dans son action induite sur { 0 , 1 } i (par permutation des coordonnées). Soit F ( G ) la classe de langages L telle que L ∩ { 0 , 1 } n est invariant sous G n . Puis toutes les langues 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}$ ont des circuits de taille au plus p o l y ( s ( G ) ) et de profondeur au plus p o l y ( log ( s ( G ) ) , ce qui est essentiellement serré.$\mathcal{F}(G)$$poly(s(G))$$poly(\log(s(G))$

$NP$$coAM$$GI$$NP$$PH$$NP$$PP$

Arvind, V., Vinodchandran, NV La complexité de comptage des langages définissables en groupe . Théorète. 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$

Enfin, le programme Mulmuley-Sohoni Geomectric Complexity Theory consiste essentiellement à utiliser la symétrie pour prouver la dureté, bien que la connexion symétrie-dureté y soit plus subtile et moins directe.

Les instances SAT structurées, qui présentent beaucoup de symétries, semblent plus faciles à résoudre que les instances SAT aléatoires. L'encodage de problèmes du monde réel dans SAT donne toujours lieu à des instances structurées (ce qui n'est pas surprenant, car les problèmes du monde réel auxquels nous sommes confrontés ont des symétries). Les meilleurs solveurs SAT complets sont capables de résoudre efficacement des instances du monde réel avec jusqu'à 1 000 000 de variables, mais aucune, à ma connaissance, ne peut résoudre efficacement des instances aléatoires avec, disons, 10 000 variables (sur Edward A. Hirsch page d'accueil, il est possible de trouver des instances aléatoires étonnamment petites, contre lesquelles même les meilleurs solveurs SAT complets sont bloqués). Ainsi, d'un point de vue empirique, la présence de symétries semble diminuer la dureté.