Действительно ли алгоритм

У меня есть (надеюсь, простой, возможно, глупый) вопрос об исторической работе Бабая, показывающей, что является квазиполиномиальным.$\mathsf{GI}$

Бабай показал, как получить сертификат, что два графа для i ∈ { 1 , 2 } изоморфны по времени, квазиполиномиальны по v = | V я | ,$G_i=(V_i,E_i)$$i\in\{1,2\}$$v=|V_i|$

Действительно ли Бабай показал, как найти элемент который переставляет вершины из G 1 в G 2 , или сертификат является просто утверждением о существовании?$\pi\in S_v$$G_1$$G_2$

Если оракул говорит мне, что и G 2 изоморфны, нужно ли мне просматривать все v ! перестановки вершин?$G_1$$G_2$$v!$

Я спрашиваю, потому что я также думаю об эквивалентности узлов. Насколько я знаю, это не известно , будет, но сказать , обнаружение тривиального были в . На самом деле, нахождение последовательности движений Рейдемейстера, которые развязывают узел, может занять экспоненциальное время ...$\mathsf{P}$

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

Более конкретно к алгоритму Бабая: да, алгоритм не только находит изоморфизм, он находит генераторы группы автоморфизмов (и, следовательно, эффективно находит все изоморфизмы) как часть алгоритма, то есть без сокращения ответа домоторпа.

С точки зрения принятия решения о существовании изоморфизма (или отсутствия связи) против его фактического поиска, ключевое слово для поиска - «поиск против решения» или «поиск до решения» («сокращение поиска до решения» и т. Д.). Такое сокращение известно для изоморфизма графов, а также для NP-полных задач, но это открытый вопрос для более алгебраических структур, таких как группы, и, я полагаю, узлов, именно потому, что мы не знаем, как добавить "гаджеты "как в ответе домоторпа.