Трудный бит

Определение

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