Wykres Izomorfizm i ukryte podgrupy

Próbuję zrozumieć związek między izomorfizmem grafu a problemem ukrytej podgrupy. Czy jest na to dobre odniesienie?

Odniesienia można znaleźć w odpowiedzi Martinschwarz, ale oto podsumowanie kilku redukcji.

Grupa symetryczna $S_n$ działa na wykresach n wierzchołków poprzez permutację wierzchołków. Ustalenie, czy dwa wykresy są izomorficzne, jest równoznaczne z czasem wielomianowym do obliczenia zestawu generującego wielkość wielomianową dla $Aut(G)$ .

Redukcja do HSP w grupie symetrycznej $S_n$ (gdzie $n$ jest liczbą zmiennych na wykresie). Funkcja $f$ jest $f(p)=p(G)$ w którym $p$ jest permutacyjny $S_n$ i $p(G)$ jest permutacji wersja $G$ . Zatem $f$ jest stałe dla cewek $Aut(G)$ i odrębne dla różnych cosetów (zwróć uwagę, że obraz $f$ składa się ze wszystkich wykresów izomorficznych do $G$ ). Ponieważ ukrytą podgrupą jest dokładnie $Aut(G)$ , gdybyśmy mogli rozwiązać ten HSP, mielibyśmy zestaw generujący dla $Aut(G)$, co jest wszystkim, czego potrzebujemy do rozwiązania GI (patrz wyżej).

Zmniejszenie HSP przez . Jeśli chcemy wiedzieć, czy dwa wykresy i na wierzchołkach są izomorficzne, rozważmy wykres który jest rozłącznym połączeniem i na wierzchołkach . Niech działa na wierzchołki, zamieniając pomocą dla . Albo lub . Tak jak poprzednio, niech gdzie G H N K G H 2 n Z / 2 Z i n + i i = 1 , . . . , n A u t ( K ) = A u t ( G ) × A u t ( H ) A u t ( K ) = ( $S_n \wr \mathbb{Z}/2\mathbb{Z}$$G$$H$$n$$K$$G$$H$$2n$$\mathbb{Z}/2\mathbb{Z}$$i$$n+i$$i=1,...,n$$Aut(K) = Aut(G) \times Aut(H)$ f ( x ) = x ( K ) x S n ≀ Z / 2 Z K f A u t ( K ) A u t ( K ) G H $Aut(K) = (Aut(G) \times Aut(H)) semidirect \mathbb{Z}/2\mathbb{Z}$$f(x)=x(K)$$x$jest teraz elementem który działa na zgodnie z opisem. Ukryta podgrupa powiązana z to dokładnie , jak w poprzedniej redukcji. Jeśli rozwiążemy ten HSP, otrzymamy zestaw generujący dla . Łatwo jest wtedy sprawdzić, czy zestaw generujący zawiera element, który zamienia kopię z kopią wewnątrz (ma nietrywialny komponent ).$S_n \wr \mathbb{Z}/2\mathbb{Z}$$K$$f$$Aut(K)$$Aut(K)$$G$$H$$K$$\mathbb{Z}/2\mathbb{Z}$

Możesz przeczytać najnowszy post Dave'a Bacona na blogu o Graph Isomorphism z linkami do literatury.

„Algorytmy kwantowe dla problemów algebraicznych” Andrew Childsa i Wima van Dam arXiv: 0812.0380 to bardzo dobry artykuł ankietowy, który zawiera dobre wprowadzenie do nie-abelowego HSP i jego związku z izomorfizmem grafowym.