#### Определение

$\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.

***