Is "Is a permutation p an automorphism of a graph in my set?" NP-complete? Suppose we have a set S of graphs (finite graphs, but an infinite number of them) and a group P of permutations that acts on S.

Instance: A permutation p in P.
Question: Does there exist a graph g in S that admits the automorphism p?

Is this problem NP-complete for some sets S?
It would be easy to check that a graph admits the permutation p (i.e. certificate).  Moreover, it's easy to find examples of S where the problem is not NP-complete, such as S being the set of complete graphs, whence the answer is always yes.
Note: I'm not really interested in what type of graphs they are; if you like they can be non-simple, directed, coloured, etc.
ADDENDUM:  The problem I'm currently looking at is classifying which isotopisms are autotopisms of Latin squares (which can also be interpreted as a special type of graph automorphism).
Given a Latin square L(i,j) we can construct a graph in the following way:

The vertex set is the set of cells (i,j) in the matrix and
There is an edge between distinct (i,j) and (i',j') whenever i=i' or j=j' or L(i,j)=L(i',j').

Such a graph is called a Latin square graph (see e.g. this article by Bailey and Cameron http://designtheory.org/library/encyc/topics/lsee.pdf).  We can interpret an autotopism of a Latin square as an automorphism of the Latin square graph.  So let S be the set of Latin square graphs formed from the Latin squares of order n.  So the question I'm interested in is:

Given a permutation p, is p an automorphism of one (or more) of the graphs in S?

My feeling is that it is a difficult question to answer in general -- I'm currently writing a 30+ page paper on the matter (with 2 co-authors).  Actually most of the time it is easy (most of the time it's &quot;no&quot;), but there are some difficult cases.
So I'm interested in finding decision problems that would be related to &quot;symmetry classification&quot;.  They don't really need to be related to Latin squares, I'm just hoping to use these techniques to answer the question for Latin squares.
Take any language $L$ (that consists of binary strings). Construct the set $S$ of graphs as follows:


For each string $x \in L$ with $|x| = n$, we have the graph $G_x = (V_x,E_x)$ in $S$, with the set of nodes $V_x = \{1,2,...,3n\}$ and the following edges: if bit $i$ of $x$ is $0$, then the nodes $3i-2$ and $3i-1$ are adjacent, otherwise $3i-2$ and $3i$ are adjacent. There are no other edges.


Now let $p$ be a permutation of $\{1,2,...,3n\}$. Assume that $p$ is an automorphism of some graph in $S$. That is, $p$ is an automorphism of $G_y$ for some $y \in L$. Let $i \in \{1,2,...,n\}$. Let us consider the following two cases:


$p(3i-2) = 3i-1$, $p(3i-1) = 3i-2$, $p(3i) = 3i$. Then we must have bit $i$ of $y$ equal to $0$.
$p(3i-2) = 3i$, $p(3i-1) = 3i-1$, $p(3i) = 3i-2$. Then we must have bit $i$ of $y$ equal to $1$.


Hence if we can solve the question "is a given $p$ automorphism of some $G \in S$", we can also solve the question "is a given string $y$ in $L$". Moreover, if we can do the former in, say, polynomial time in $|p|$, we can do the latter in polynomial time in $|y|$ as well.

Now you can just let $L$ be your favourite NP-hard problem. Or the halting problem...