Вычислительная неотличимость
Определение
$\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$ -- схема полиномиального размера.
Свойства вычислительной неотличимости
- Вычислительная неотличимость -- отношение эквивалентности.
- $\alpha_n \sim \beta_n \Rightarrow \alpha_n \gamma_n \sim \beta_n \gamma_n$ для любой $\gamma_n$, независимой от $\alpha_n$ и $\beta_n$.
- $\alpha_n \sim \beta_n \Rightarrow C_n(\alpha_n) \sim C_n(\beta_n)$, $C_n$ -- схема полиномиального размера.