cuáles son los límites conocidos de la complejidad del automorfismo de gráficos no triviales

Dado cualquier gráfico G no dirigido simple, no es trivial determinar si G tiene automorfismos no triviales (no identitarios). Pero, ¿cuáles son los resultados en los límites superior / inferior de este problema de decisión?

Determinar si un gráfico tiene un automorfismo no trivial Cook-reduce (tiempo polinómico Turing) a isomorfismo gráfico (determinar si un par de gráficos es isomorfo) (ejercicio para el lector). No se sabe que sea equivalente al isomorfismo gráfico.

A su vez, el isomorfismo gráfico se puede resolver en tiempo y se encuentra en . En particular, no es completo a menos que la jerarquía polinómica se colapse.$2^{\tilde O(\sqrt{n})}$$NP \cap coAM$$NP$