Soient p un nombre premier, S un sous-ensemble de F_p et H une famille de polynômes à coefficients dans F_p et de degré inférieur à d. Quel est-alors le plus grand entier k tel que pour toutes paires de sous-ensembles de F_p, disjoints A,B dont le cardinal de l'union est k, il existe un polynôme P appartenant à H tel que P(x) soit dans S si x est dans A et P(x) n'appartienne pas à S si x est dans B? Ce problème correspond à l'étude de la complexité de certaines familles pseudo-aléatoires. On commencera par donner la définition de cette complexité puis nous exposerons les différents résultats obtenus selon la nature des ensembles S et H étudiés. Il s'agit de travaux réalisés avec R. Balasubramanian, Elie Mosaki et Andras Sarkozy