Семейство распределений вероятностей $(\mathfrak D_i\,|\, i\in I)$ на множестве $\{0,1\}^*$, где $I\subseteq\mathbb N$ или $I\subseteq\{0,1\}^*$, называется полиномиально конструируемым, если существует полиномиальный вероятностный алгоритм $\mathcal G$ такой, что для любого $i\in I$ случайная величина $\mathcal G\left(1^i\right)$ (при $I\subseteq\mathbb N$) или $\mathcal G(i)$ (при $I\subseteq\{0,1\}^*$) имеет распределение $\mathfrak D_i$.