Let $G$ be a finite group, and consider a permutation representation of $G$ on some finite set $\Sigma$ with $|\Sigma| = n$. By considering the vector space $V$ over $\mathbf{C}$ of dimension $n$ generated by the elements of $\Sigma$, one obtains a representation $V$ of $G$ with character which we denote by $\chi_{\Sigma}$.
Problem: If one is only given a character $\chi$ of $G$, what is the easiest way to tell whether it is equal to $\chi_{\Sigma}$ for some permutation representation $\Sigma$ of $G$?
Some Remarks: It seems to be a quite stringent condition. The character $\chi$ must be valued in $\mathbf{Z}$. Indeed, $\chi$ must extend to the character of $S_n$ given by the trivial plus the standard representation.
A Caution : Suppose that $G = D_8$ is the dihedral group of order $8$, and $H = Q_8$ is the quaternion group of order $8$. Then the character tables of $G$ and $H$ are the same. In particular, the inclusion $G \rightarrow S_4$ gives rise to a character $\chi$ of $G$ which does come from a permutation representation, but the "corresponding" character of $H$ does not. So the answer must involve knowing more than the character table of $G$.
Tautologies : Clearly, given $\chi$, one can simply "compute" all the permutation representations of $G$, and see if $\chi = \chi_{\Sigma}$ for any such representations that arise, but this is not necessarily practical.