Consider the following two algorithmic problems - one of determining whether two graphs are isomorphic and the other of determining if a graph has a nontrivial automorphism:
(1) Decision problem: Graph isomorphism. Instance: Graphs $G$ and $H$. Question: Is $G \cong H$?
(2) Decision problem: Nontrivial automorphism group. Instance: A graph $G$. Question: Is $Aut(G)>1$.
An article I'm reading ([P. J. Cameron, "Automorphisms of graphs,'' Chapter 5, Topics in Algebraic Graph Theory]) says that if we can solve (1), then we can solve (2) "by attaching distinctive `gadgets' at each vertex and checking whether any pair of the resulting graphs are isomorphic.''
For example, if $G$ is the 4-cycle graph on vertices $a,b,c,d$, then, we can attach the cycle graphs $C_5, C_6, C_7, C_8$ to $a,b,c,d$, respectively, to get a graph $G'$. We can attach $C_7, C_6, C_5, C_8$, to $a,b,c,d$, respectively, to get a graph $G''$. If $G' \cong G''$, then $(a,c)$ is an automorphism of $G$.
It seems to me that to solve (2) the number of pairs to check for isomorphism is superexponential and on the order of $n!$ at first thought, where $n$ is the number of vertices of $G$. Is it true that (2) does not have the same complexity as (1), at least given just this proof of attaching gadgets?
Take an "appropriate" gadget $X$ and for a vertex $v \in V(G)$, let $H_v$ be the graph you obtain by attaching $X$ at $v$.
A nontrivial automorphism of $G$ exists if and only if there are $u, v \in V(G)$ and $v \ne u$ with $H_v \cong H_u$. You need only run the isomorphism algorithm at most $O(|V(G)|^2)$ times to get your answer.
So, if the first problem is polynomial so is the second.