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?
what are known bounds on complexity of nontrivial graph automorphism
cc.complexity theory;graph isomorphism;automorphism