可忽略函数

在数学中，可忽略函数（）是指
对于一个函数  ，如果对于任意一个正多项式，存在一个，使得对于所有的
那么这个函数便是可忽略的（negligible）。通常我们把“存在一个，使得对于所有的”简化为“对于所有足够大的”。

历史
可忽略函数这个概念是和数学分析的形式化模型相关的。第一个比较严格的定义是波尔查诺在1817年给出的。后来的柯西, 魏尔施特拉斯和海涅都用了基本相同的以下定义：

（连续函数） 一个实数函数在处连续，当对于任意一个正实数，有一个正实数，使时，有。

只要每步改变一项参数，此定义就可经数步转换成为可忽略函数的定义。首先，当时，我们需要定义"足够大"（sufficiently large），并定义無窮小量：

（足够大） 实数足够大时一个数学命题为真，当且仅当存在一个实数，对所有的实数此数学命题为真。

（无穷小） 一个连续函数无穷小，当对任意足够大的正实数，对任意正实数 ，有
。

然后我们把正实数换成正实数多项式函数。

（可忽略函数） 一个连续函数可忽略，当对任意足够大的正实数，对任意正多项式，有
。

在基于計算複雜性理論的现代密码学中，一个安全技术是数学上可证明安全（provably secure）的意思通常是，此安全技术的失败的概率是关于密钥长度的一个可忽略函数（参见公钥密码学）。因为密钥长度肯定是自然数，这就是为什么开篇的定义把定义域改为自然数域的原因。

注释

 参考 







Category:数学分析
Category:各种类函数