Grupowanie izomorfizmu do izomorfizmu grafowego

Czytając niektóre blogi o złożoności obliczeniowej (na przykład tutaj ) przyswoiłem sobie pogląd, że podjęcie decyzji, czy dwie grupy są izomorficzne jest łatwiejsze niż przetestowanie dwóch wykresów pod kątem izomorfizmu. Na przykład na podanej stronie napisano, że izomorfizm grafów jest bardziej ogólnym problemem niż izomorfizm grupowy.

Dlatego stawiam następujące

Biorąc pod uwagę grupę ktoś może podać konstrukcję wykresu wielomianu wielkości wtakie, że dla grup i$G$$\Gamma(G)$$|G|$

$$\Gamma(G) \cong \Gamma(H) \iff G \cong H$$ $G$$H?$

Redukcję opisano w klasycznej pracy Millera.

Nie tak szybko. Czai się tu wielka niejednoznaczność:

Jak wprowadzasz swoją grupę do obliczeń?

W przeciwieństwie do wykresów, grupy mogą być wprowadzane jako środki, które różnią się znacznie pod względem wielkości wejściowej i wynikającej z tego złożoności. Wersja cytowana w Millerze jest jedną z najmniej naturalnych i na przykład nie znajdziesz jej w systemie algebry komputerowej, takiej jak GAP, Magma lub Sage. Więc choć ma teoretyczną przesłankę, nazwanie tego problemu rozwiązaniem byłoby zbyt daleko.

1. Generatory i relacje: Izomorfizm grupy jest nierozstrzygalny (izomorfizm wykresu jest rozstrzygalny).

$G$$G=1$

W przypadku grup wprowadzanych przez generatory i relacje: izomorfizm grup jest trudniejszy niż izomorfizm grafów, w rzeczywistości jest niezdecydowany.

2. Dane wejściowe wykorzystywane przez systemy oprogramowania: izomorfizm grup permutacji, a grupy matryc są co najmniej tak trudne jak izomorfizm grafów (nie na odwrót).

$p$

Dla grup wejściowych dla systemów oprogramowania: grupowy izomorfizm jest co najmniej tak trudny jak izomorfizm grafowy.

3. Teoretyczne dane wejściowe dotyczące złożoności: w przypadku danych wejściowych grupy czarnych skrzynek nie wiadomo, że izomorfizm grupy występuje w NP lub w ko-NP (izomorfizm wykresu występuje w obu przypadkach).

$\Sigma^2$$f:G\to H$$G$$H$$f$jest prawidłowym homomorfizmem. Wydaje się, że potrzebujesz przynajmniej prezentacji grup, a nie jest to łatwe do uzyskania.

Dla grup czarnych skrzynek: izomorfizm grup jest co najmniej tak samo trudny jak izomorfizm grafów.

4. Dane wejściowe do tabeli Cayley.

Kiedyś w latach 70. Tarjan, Pultr-Hederlon, Miller i inni zauważyli, że grupy wprowadzone przez ich całą tabliczkę mnożenia można również traktować jako wykresy. W ten sposób izomorfizm grupowy redukuje się do izomorfizmu grafowego w czasie wielomianowym. Miller poszedł znacznie dalej, obserwując, że wiele struktur kombinatorycznych robi to samo, na przykład Steiner potroił. Wykazał również, że izomorfizm półgrupowy jest równoważny izomorfizmowi grafowemu.

$n^{O(\log n)}$

Dla tabel Cayley'a: izomorfizm grupy redukuje się do izomorfizmu grafowego.

$n$$O((\log n)^3)$

$n$$O(n^2 \log n)$