可忽略函數

在數學中，可忽略函數（英語：Negligible function）是指

對於一個函數 ${\displaystyle \mu (x):\mathbb {N} {\rightarrow }\mathbb {R} }$ ，如果對於任意一個正多項式${\displaystyle poly()}$，存在一個${\displaystyle N_{c}>0}$，使得對於所有的${\displaystyle x>N_{c}}$

${\displaystyle \mu (x)<{\frac {1}{poly(x)}}}$

那麼這個函數便是可忽略的（negligible）。通常我們把「存在一個${\displaystyle N_{c}>0}$，使得對於所有的${\displaystyle x>N_{c}}$」簡化為「對於所有足夠大的${\displaystyle x}$」。

歷史

可忽略函數這個概念是和數學分析的形式化模型相關的。^{[註 1]}第一個比較嚴格的定義是波爾查諾在1817年給出的。後來的柯西, 魏爾施特拉斯和海涅都用了基本相同的以下定義^{[註 2]}：

（連續函數） 一個實數函數${\displaystyle f(x)}$在${\displaystyle x=x_{0}}$處連續，當對於任意一個正實數${\displaystyle \epsilon >0}$，有一個正實數${\displaystyle \delta >0}$，使${\displaystyle |x-x_{0}|<\delta }$時，有${\displaystyle |f(x)-f(x_{0})|<\epsilon }$。

只要每步改變一項參數，此定義就可經數步轉換成為可忽略函數的定義。首先，當${\displaystyle x_{0}=\infty ,f(x_{0})=0}$時，我們需要定義"足夠大"（sufficiently large），並定義無窮小量：

（足夠大） 實數${\displaystyle x}$足夠大時一個數學命題為真，當且僅當存在一個實數${\displaystyle N_{c}>0}$，對所有的實數${\displaystyle x>N_{c}}$此數學命題為真。

（無窮小） 一個連續函數${\displaystyle \mu (x)}$無窮小，當對任意足夠大的正實數${\displaystyle x}$，對任意正實數^{[註 3]} ${\displaystyle pnum={\frac {1}{\epsilon }}>0}$，有

${\displaystyle |\mu (x)|<\epsilon ={\frac {1}{pnum}}}$。

然後我們把正實數${\displaystyle \epsilon }$換成正實數多項式函數${\displaystyle \epsilon (x)}$。^{[註 4]}

（可忽略函數） 一個連續函數${\displaystyle \mu (x)}$可忽略，當對任意足夠大的正實數${\displaystyle x}$，對任意正多項式${\displaystyle poly(x)={\frac {1}{\epsilon (x)}}>0}$，有

${\displaystyle |\mu (x)|<\epsilon (x)={\frac {1}{poly(x)}}}$。

在基於計算複雜性理論的現代密碼學中，一個安全技術是數學上可證明安全（provably secure）的意思通常是，此安全技術的失敗^{[註 5]}的概率是關於密鑰長度${\displaystyle x=n}$的一個可忽略函數（參見公鑰密碼學）。因為密鑰長度${\displaystyle n}$肯定是自然數，這就是為什麼開篇的定義把定義域改為自然數體的原因。^{[註 6]}