Czy algorytm quasiipolomialnego czasu Babai faktycznie generuje izomorfizm?

13

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. $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? $\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_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}$

graph-isomorphism search-problem

— Znaki
źródło

28

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 rozmiarze $n+1$ $n$ $n+2$ $n+1,\ldots n+n$ zwisające z ich wierzchołków, co czyni izomorfizm wyjątkowym.

— domotorp
źródło

1

Dzięki! Czy podobne gadżety działałyby, by pokazać zestaw ruchów Reidemeistera, które wiążą dwa węzły, biorąc pod uwagę, że są one sobie równe, czy też nie jest to znane?

— Mark S

3

Wątpię, ponieważ w tym przypadku nie widzę sposobu na „zrujnowanie” możliwego rozwiązania.

— domotorp

17

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.

— Joshua Grochow
źródło