ハードコア述語
述語 b : { 0 , 1 } ∗ → { 0 , 1 } {\displaystyle b:\{0,1\}^{*}\to \{0,1\}} が以下を満たすとき、関数 f のハードコア述語であるという:
b は多項式時間で計算可能。すなわちある多項式時間アルゴリズム B が存在して, B ( x ) = b ( x ) {\displaystyle B(x)=b(x)} 。
任意の多項式サイズ回路族 { C n } {\displaystyle \{C_{n}\}} について, ある無視可能函数 ε が存在し,
P r [ x ← R { 0 , 1 } n : C n ( f ( x ) ) = b ( x ) ] < 1 2 + ε ( n ) {\displaystyle Pr[x\gets _{R}\{0,1\}^{n}:C_{n}(f(x))=b(x)]<{\frac {1}{2}}+\epsilon (n)}