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?
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?
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 wNP∩coAM. W szczególności, nie jestNP-Complete chyba że wielomian hierarchia zwija.