Created about 12 years ago, updated 5 months ago
ID278
Определение
$\beta(x)$ - трудный бит для $f$, если
$$
\forall p\ \forall \{C_n\}\ \exists N\ \forall n > N\ |Pr\{C_n(f(x)) = \beta(x)\} - \frac{1}{2}| < \frac{1}{p(n)}
$$
Предположительный пример трудного бита
Функция Рабина: $(x,\ y) \mapsto (x^2\ mod\ y,\ y)$. Трудным битом считается чётность x.
#### Определение
$\beta(x)$ - **трудный бит** для $f$, если
$$
\forall p\ \forall \{C_n\}\ \exists N\ \forall n > N\ |Pr\{C_n(f(x)) = \beta(x)\} - \frac{1}{2}| < \frac{1}{p(n)}
$$
***
#### *Предположительный* пример трудного бита
**Функция Рабина**: $(x,\ y) \mapsto (x^2\ mod\ y,\ y)$. Трудным битом считается чётность x.
***
