Est-ce que l'algorithme quasipolynomial time Babai génère réellement l'isomorphisme?

J'ai une question (espérons-le simple, peut-être stupide) sur le document historique de Babai montrant que est quasipolynomial.$\mathsf{GI}$

Babai a montré comment produire un certificat que deux graphes pour sont isomorphes, en temps quasi-polynomial dans.$G_i=(V_i,E_i)$$i\in\{1,2\}$$v=|V_i|$

Babai a-t-il réellement montré comment trouver un élément qui permute les sommets de à , ou le certificat est-il simplement une déclaration d'existence?$\pi\in S_v$$G_1$$G_2$

Si un oracle me dit que et sont isomorphes, dois-je encore parcourir tous lespermutations des sommets?$G_1$$G_2$$v!$

Je demande parce que je pense aussi à l'équivalence des nœuds. Pour autant que je sache, ce n'est pas connu, mais disons que la détection du dénouement était dans . En fait, trouver une séquence de mouvements Reidemeister qui défait le nœud pourrait encore prendre un temps exponentiel ...$\mathsf{P}$

Ces problèmes sont polynomialement équivalents. En effet, supposons que vous ayez un algorithme qui puisse décider si deux graphes sont isomorphes ou non, et il prétend qu'ils le sont. Attachez une clique de taille à un sommet arbitraire de chaque graphique. Testez si les graphiques résultants sont isomorphes ou non. S'ils le sont, alors nous pouvons conclure qu'il existe un isomorphisme qui mappe les sommets respectifs les uns aux autres, nous pouvons donc les supprimer. En répétant ce test n fois, nous pouvons trouver une image (possible) pour n'importe quel sommet. Après cela, nous attachons une autre clique, cette fois de taille n + $n+1$$n$$n+2$à un sommet (différent) arbitraire de chaque graphe d'origine, et procéder comme avant, etc. Finalement, nous finirons avec deux graphes isomorphes, avec des cliques de taille suspendues à leurs sommets, ce qui rend l'isomorphisme unique.$n+1,\ldots n+n$

Plus spécifique à l'algorithme de Babai: oui, l'algorithme trouve non seulement un isomorphisme, il trouve des générateurs du groupe d'automorphisme (et donc trouve effectivement tous les isomorphismes) dans le cadre de l'algorithme, c'est-à-dire sans la réduction de la réponse de domotorp.

En termes de détermination de l'existence d'un isomorphisme (resp., Dénouement) par rapport à sa recherche effective, le mot-clé à rechercher est "recherche vs décision" ou "réduction de la recherche à la décision" ("réduction de la recherche à la décision", etc.). Une telle réduction est connue pour l'isomorphisme des graphes, ainsi que pour les problèmes NP-complets, mais est une question ouverte pour des structures plus algébriques telles que les groupes et, je crois, les nœuds, précisément parce que nous ne savons pas comment ajouter des "gadgets" "comme dans la réponse de domotorp.