co wiadomo ogranicza złożoność nietrywialnego automorfizmu grafów

Biorąc pod uwagę dowolny prosty niekierowany wykres G, nie jest łatwe ustalenie, czy G ma nietrywialne (nieidentyfikacyjne) automorfizmy. Ale jakie są wyniki w górnej / dolnej granicy tego problemu decyzyjnego?

cc.complexity-theory graph-isomorphism automorphism Charles Yu
źródło

Odpowiedzi:

Ustalanie, czy wykres ma nietrywialny automorfizm Cook-zmniejsza (wielomianowy czas Turinga) do izomorfizmu grafów (określa, czy para wykresów jest izomorficzna) (ćwiczenie dla czytelnika). Nie wiadomo, że jest równoważny izomorfizmowi grafowemu.

Z kolei izomorfizm grafów można rozwiązać w razem i leży w. W szczególności, nie jest-Complete chyba że wielomian hierarchia zwija. $2^{\tilde O(\sqrt{n})}$ $NP \cap coAM$ $NP$

Joshua Grochow
źródło

G A \in P^{G I}

$GA\in P^{GI}$

G A

$GA$

G I

$GI$

G I \in B P P^{G A}

$GI\in BPP^{GA}$