Полиномиально вычислимый предикат $b: \cup_{i\in I}\Sigma^i \rightarrow \Sigma$ называется трудным для функции $f$, если вероятность угадать предикат пренебрежимо мало отличается от $\frac{1}{2}$: $$ \exists N~\forall n > N:~Pr(A(f(u_n)) = b(u_n)) < \frac{1}{2} + \frac{1}{p(n)} $$