Grupowanie izomorfizmu do izomorfizmu grafowego

12

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|$
$Γ (sol) ≅ Γ (H.) ⟺ sol ≅ H.$ $\Gamma(G) \cong \Gamma(H) \iff G \cong H$ $G$ $H?$

complexity-theory graph-isomorphism group-theory

— Jernej
źródło

podczas gdy oba są ze sobą ściśle powiązane, jak zauważono i badano przez dziesięciolecia, afektywny izomorfizm grupy nie jest tak naprawdę udowodniony, że jest „łatwiejszy” niż izomorfizm grafowy, tj. jest to w przybliżeniu główne otwarte pytanie, w jaki sposób ich złożoność jest dokładnie powiązana. byłoby również pomocne, gdybyś wyraził związek matematyczny również słowami.

— vzn

12

Redukcję opisano w klasycznej pracy Millera.

— Yuval Filmus
źródło

4

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.

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.

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.

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.

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)$

— Algeboy
źródło

Dziękuję za wszystkie pomocne dyskusje. Jeden punkt: gdzie piszesz „W przypadku grup danych wejściowych dla systemów oprogramowania: izomorfizm grup jest trudniejszy niż izomorfizm grafów”, czy masz powód do twierdzenia, że jest trudniejszy (a nie że jest co najmniej tak samo trudny )? „Twardszy” sugerowałby, że złożoność nie jest równa. Czy są na to jakieś dowody? A może miałeś na myśli „co najmniej tak samo”?

— DW

Ups, wstyd mnie, „przynajmniej tak mocno, jak” byłoby to, co wiadomo. Ścisła nierówność w złożoności jest, jak mówisz - rzadka. Można jednak zauważyć, że problemy takie jak równoważność kodu (związane z izomorfizmem hipergraphowym) są zwykle problemem, który można zredukować do izomorfizmu grupowego w tych modelach. Równoważność kodu pozostaje złożonością wykładniczą nawet po przełamaniu Babai przez izomorfizm grafów w czasie quasi-wielomianowym. Daje to słabe dowody na „trudniejsze”, ale nie jest znany żaden dowód na „silniej”. Poprawię powyższe. Dzięki.

— Algeboy