# Finding the smallest set on which a group acts faithfully

Given a finite group $G$, how efficient can one make an algorithm to find the size of the smallest set $S$ such that $G$ is isomorphic to a group of permutations of the members of $S$? And does the answer change if one requires the output to specify not only the cardinality of $S$ but the particular action of $G$ on $S$? Might this be an NP-hard problem? Or is it a trivial thing whose solution is known to everyone on earth except me? Or somewhere in between?

-
What's trivial are the bounds that $\#G$ divides $\#S!$ and $\#S\le \#G$ or that the answer for cyclic $G$ of order $\prod p^{k_p}$ is $\sum p^{k_p}$, bu tbeyond that things can get messy ... – Hagen von Eitzen Oct 11 '13 at 20:26
I think this is a difficult problem, and that there is no efficient algorithm known. It might be easier to find an action that was close to being optimal. – Derek Holt Oct 11 '13 at 21:04
Slightly less trivial is that $|S|<|G|$ except when $G$ is prime cyclic or generalized quaternion. I do remember a question about this very thing being asked on math.SE a while ago, and @JackSchmidt giving a nice summary of what's known. But I cannot find it now. – user641 Oct 11 '13 at 23:28
Here are Jack Schmidt's answers, apparently mostly on group theory: math.stackexchange.com/users/583/jack-schmidt?tab=answers – Michael Hardy Oct 11 '13 at 23:50
Also see this : math.stackexchange.com/questions/514650/… – Prahlad Vaidyanathan Oct 12 '13 at 4:04