¿El algoritmo de tiempo cuasipolinomial

Tengo una pregunta (con suerte simple, tal vez tonta) en el documento histórico de Babai que muestra que es cuasipolinomial.$\mathsf{GI}$

Babai mostró cómo producir un certificado de que dos gráficas para i ∈ { 1 , 2 } son isomorfas, en el tiempo cuasipolinomiales en v = | V i | .$G_i=(V_i,E_i)$$i\in\{1,2\}$$v=|V_i|$

¿Babai realmente mostró cómo encontrar un elemento que permute los vértices de G 1 a G 2 , o el certificado es simplemente una declaración de existencia?$\pi\in S_v$$G_1$$G_2$

Si un oráculo me dice que y G 2 son isomórficos, ¿todavía necesito revisar todos los v ! permutaciones de los vértices?$G_1$$G_2$$v!$

Pregunto porque también pienso en la equivalencia de nudos. Por lo que yo sé, no se sabe ser, pero decir detectando la unknot estaban en . En realidad, encontrar una secuencia de movimientos Reidemeister que desate el nudo aún podría llevar un tiempo exponencial ...$\mathsf{P}$

$n+1$$n$$n+2$$n+1,\ldots n+n$

Más específico para el algoritmo de Babai: sí, el algoritmo no solo encuentra un isomorfismo, sino que también encuentra generadores del grupo de automorfismos (y, por lo tanto, efectivamente encuentra todos los isomorfismos) como parte del algoritmo, es decir, sin la reducción de la respuesta de domotorp.

En términos de decidir la existencia de un isomorfismo (resp., Desanudar) frente a encontrar uno, la palabra clave para buscar es "buscar vs decisión" o "reducir la búsqueda a la decisión" ("reducir la búsqueda a la decisión", etc.). Tal reducción es conocida por el isomorfismo gráfico, así como por problemas de NP completo, pero es una pregunta abierta para estructuras más algebraicas como grupos y, creo, nudos, precisamente porque no sabemos cómo agregar "gadgets" "como en la respuesta de domotorp.