Let p be a prime number, S ⊂ Fp and P ⊂ {P ∈ Fp[X] : deg(P) ≤ d }. What is the largest integer k such that for all subsets A, B of Fp satisfying A ∩B=∅ and |A ∪B| = k, there exists P ∈ P such that P(x) ∈ S if x ∈ A and P(x) ∉ S if x ∈ B ? This problem corresponds to the study of the complexity of some families of pseudo-random subsets. Some of the proofs are based on upper bounds for exponential sums or characters sums in finite fields, other proofs use combinatorics and additive number theory.