  In this paper we are interested in the following problem. Let $p$ be a prime
number, $S\subset \F_p$ and $\cP\subset \{P\in\F_p [X]:\deg P\le d\}$. What is
the largest integer $k$ such that for all subsets $\cA, \cB$ of $\F_p$
satisfying $\cA\cap\cB =\emptyset$ and $|\cA\cup\cB |=k$, there exists
$P\in\cP$ such that $P(x)\in S$ if $x\in\cA$ and $P(x)\not\in S$ if $x\in\cB$?
This problem corresponds to the study of the complexity of some families of
pseudo-random subsets. First we recall this complexity definition and the
context of pseudo-random subsets. Then we state the different results we have
obtained according to the shape of the sets $S$ and $\cP$ considered. Some
proofs are based on upper bounds for exponential sums or characters sums in
finite fields, other proofs use combinatorics and additive number theory.
