Negligible

ここでは2の意味について解説する。正値関数 $ν(k)$ が以下を満たす時、 $ν$ は（kに関し）negligibleであるという。

任意の多項式fに対し、

$\lim_{k \to \infty}\nu(k) \cdot f(k) = 0$

すなわち任意の多項式fに対し、ある

k 0

が存在して、全ての

k > k 0

に対し、

ν(k) < 1 / f (k)

。

関数 $ν(k)$ が $k$ に関しnegligibleな時、 $\nu(k) =\varepsilon(k)$ と書く。

[編集] overwhelming

事象の列 $\{X_k\}_{k\in{\Bbb{N}}}$ が、 $1-P(X_k) =\varepsilon(k)$ となるとき、事象 $X k$ が生じる確率はkに関しoverwhelming（圧倒的）であるという。