Вычислительная неотличимость

Определение

$\alpha_n$, $\beta_n$ -- вычислительно неотличимые семейства случайных величин, если
$$\forall p(\cdot)\ \forall \{D_n\}\ \exists N\ \forall n > N\ |Pr\{D_n(\alpha_n) = 1\} - Pr\{D_n(\beta_n) = 1\}| < \frac{1}{p(n)}$$
где $p(\cdot)$ -- полином, $D_n$ -- схема полиномиального размера.

Свойства вычислительной неотличимости

1. Вычислительная неотличимость -- отношение эквивалентности.
2. $\alpha_n \sim \beta_n \Rightarrow \alpha_n \gamma_n \sim \beta_n \gamma_n$ для любой $\gamma_n$, независимой от $\alpha_n$ и $\beta_n$.
3. $\alpha_n \sim \beta_n \Rightarrow C_n(\alpha_n) \sim C_n(\beta_n)$, $C_n$ -- схема полиномиального размера.