quelles sont les limites connues de la complexité de l'automorphisme de graphes non triviaux

Étant donné tout graphe simple non orienté G, il n'est pas trivial de déterminer si G a des automorphismes non triviaux (sans identité). Mais quels sont les résultats sur les bornes supérieures / inférieures de ce problème de décision?

cc.complexity-theory graph-isomorphism automorphism Charles Yu
la source

Réponses:

Déterminer si un graphique a un automorphisme non trivial Cook-réduit (temps de polynôme Turing) à l'isomorphisme du graphique (déterminer si une paire de graphiques est isomorphe) (exercice pour le lecteur). Il n'est pas connu pour être équivalent à l'isomorphisme du graphe.

À son tour, l'isomorphisme du graphe peut être résolu en temps et se situe dans. En particulier, il n'est pascomplet sauf si la hiérarchie polynomiale s'effondre. $2^{\tilde O(\sqrt{n})}$ $NP \cap coAM$ $NP$

Joshua Grochow
la source

G A \in P^{G I}

$GA\in P^{GI}$

G A

$GA$

G I

$GI$

G I \in B P P^{G A}

$GI\in BPP^{GA}$