Complexity of algorithm to test if a graph is asymmetric Counting the order of automorphism group of a graph is polynomial-time equivalent to graph isomorphism problem. But if we just want to know if the order is greater than 1, what is the complexity of this problem? Graphs which have no automorphism except for the trivial one, that is identity permutation, are called asymmetric graphs. So the problem is to check if the graph is asymmetric.
The complement of your problem is known as graph automorphism problem (GA). It is a candidate for $NP$-intermediate problems. The problem is not known to be solvable in polynomial time. Also, It is not known to be $NP$-complete. It polynomialy reduces to the graph isomorphism problem (GI) but no known polynomial reduction from GI to GA. Unique-GI is equivalent to GA.