# what are known bounds on complexity of nontrivial graph automorphism

Given any simple undirected graph G, it is nontrivial to determine if G has nontrivial (non-identity) automorphisms. But what are results on upper/lower bounds of this decision problem?

In turn, graph isomorphism can be solved in $2^{\tilde O(\sqrt{n})}$ time and lies in $NP \cap coAM$. In particular, it is not $NP$-complete unless the polynomial hierarchy collapses.
• So $GA\in P^{GI}$? I thought $GA$ many one reduces to $GI$. Am I wrong? Also is it known $GI\in BPP^{GA}$ or is even this beyond reach? May 12, 2017 at 13:53