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?
See this MO answer for links to several important papers.
The main citation is: Johnson, D. L. "Minimal permutation representations of finite groups." Amer. J. Math. 93 (1971), 857-866.
Edit (10/30/13): Check the comment below for an entire book on this subject.