Czy algorytm quasiipolomialnego czasu Babai faktycznie generuje izomorfizm?

Mam (mam nadzieję, że proste, może głupie) pytanie na przełomowy artykuł Babai, który pokazuje, że jest quasipolynomial.$\mathsf{GI}$

Babai pokazał, jak stworzyć certyfikat, że dwa wykresy dla są izomorficzne, z czasem quasipolynomial in.i ∈ { 1 , 2 } v = | V i $G_i=(V_i,E_i)$$i\in\{1,2\}$$v=|V_i|$

Czy Babai rzeczywiście pokazać , jak znaleźć element że permutacji wierzchołków do , czy certyfikat jedynie istnienie-stwierdzenie?G 1 G $\pi\in S_v$$G_1$$G_2$

Jeśli wyrocznią mówi mi, że i są izomorficzne, czy nadal muszę przejrzeć wszystkiepermutacje wierzchołków?G 2 v $G_1$$G_2$$v!$

Pytam, ponieważ myślę również o równoważności węzłów. O ile mi wiadomo, nie jest to znane, ale powiedzmy, że wykrywanie unknot było w . Właściwie znalezienie sekwencji ruchów Reidemeister, które rozwiążą węzeł, może jeszcze potrwać wykładniczo ...$\mathsf{P}$

Te problemy są wielomianowo równoważne. Rzeczywiście, załóżmy, że masz algorytm, który może zdecydować, czy dwa wykresy są izomorficzne, czy też nie, i twierdzi, że są. Dołącz klikę o rozmiarze do dowolnego wierzchołka każdego wykresu. Sprawdź, czy uzyskane wykresy są izomorficzne, czy nie. Jeśli tak, to możemy stwierdzić, że istnieje izomorfizm, który odwzorowuje odpowiednie wierzchołki względem siebie, a zatem możemy je usunąć. Powtarzając ten test razy, możemy znaleźć (możliwy) obraz dla dowolnego wierzchołka. Następnie dołączamy kolejną klikę, tym razem o rozmiarze do (innego) dowolnego wierzchołka każdego oryginalnego wykresu i postępujemy jak poprzednio itp. W końcu otrzymamy dwa wykresy, które są izomorficzne, z klikami o rozmiarzen n + 2 n + 1 , … n + $n+1$$n$$n+2$$n+1,\ldots n+n$ zwisające z ich wierzchołków, co czyni izomorfizm wyjątkowym.

Bardziej konkretnie dla algorytmu Babai: tak, algorytm nie tylko znajduje izomorfizm, ale także generatory grupy automorfizmów (a zatem skutecznie znajduje wszystkie izomorfizmy) jako część algorytmu, to znaczy bez zmniejszenia odpowiedzi domotorp.

Pod względem decydowania o istnieniu izomorfizmu (odpowiednio, cofanie węzłów) w porównaniu do faktycznego jego znalezienia, słowem kluczowym do wyszukania jest „wyszukiwanie vs decyzja” lub „wyszukiwanie do zmniejszenia decyzji” („ograniczenie wyszukiwania do decyzji” itp.). Taka redukcja znana jest z izomorfizmu grafów, a także z problemów związanych z NP-zupełnością, ale jest otwartym pytaniem o więcej struktur algebraicznych, takich jak grupy, i, jak sądzę, węzłów, właśnie dlatego, że nie wiemy, jak dodać „gadżety” „jak w odpowiedzi domotorp.