查看“︁可忽略函数”︁的源代码

{{NoteTA
|G1 = Math
|1 = zh-cn:程序; zh-tw:程式;
}}
在[[数学]]中，'''可忽略函数'''（{{lang-en|Negligible function}}）是指
<onlyinclude>
:对于一个[[函数]] <math>\mu(x):\mathbb{N}{\rightarrow}\mathbb{R}</math> ，如果对于任意一个正多项式<math>poly()</math>，存在一个<math>N_c>0</math>，使得对于所有的<math>x>N_c</math>
::<math>\mu(x)<\frac{1}{poly(x)}</math>
</onlyinclude>
那么这个函数便是'''可忽略的'''（negligible）。通常我们把“存在一个<math>N_c>0</math>，使得对于所有的<math>x>N_c</math>”简化为“对于所有足够大的<math>x</math>”。

==历史==
'''可忽略函数'''这个概念是和[[数学分析]]的形式化模型相关的。{{notetag|尽管“[[连续函数]]”和“[[无穷小]]”的概念在[[艾萨克·牛顿|牛顿]]和[[莱布尼茨]]时代（十七世纪八十年代）就有了，但直到十九世纪一十年代才为后来的数学家们给出严格的数学定义。}}第一个比较严格的定义是[[伯恩哈德·波爾查諾|波尔查诺]]在1817年给出的。后来的[[奧古斯丁·路易·柯西|柯西]], [[卡尔·魏尔施特拉斯|魏尔施特拉斯]]和[[愛德華·海涅|海涅]]都用了基本相同的以下定义{{notetag|其中所有数都在[[实数域]]<math>\mathbb{R}</math>中}}：

:'''（[[连续函数]]）''' 一个实数函数<math>f(x)</math>在<math>x=x_0</math>处''连续''，当对于任意一个正实数<math>\epsilon>0</math>，有一个正实数<math>\delta>0</math>，使<math>|x-x_0|<\delta</math>时，有<math>|f(x)-f(x_0)|<\epsilon</math>。

只要每步改变一项参数，此定义就可经数步转换成为'''可忽略函数'''的定义。首先，当<math>x_0=\infty, f(x_0)=0</math>时，我们需要定义"''足够大''"（sufficiently large），并定义[[無窮小量]]：

:'''（足够大）''' 实数<math>x</math>''足够大''时一个数学命题为真，当且仅当存在一个实数<math>N_c>0</math>，对所有的实数<math>x>N_c</math>此数学命题为真。

:'''（[[无穷小]]）''' 一个连续函数<math>\mu(x)</math>''无穷小''，当对任意足够大的正实数<math>x</math>，对任意正实数{{notetag|注意此处的倒数<math>pnum</math>在定义域为实数域时并不需要加入，这样写是为了推导时看得清楚。}} <math>pnum=\frac{1}{\epsilon}>0</math>，有
::<math>|\mu(x)|<\epsilon=\frac{1}{pnum}</math>。

然后我们把正实数<math>\epsilon</math>换成正实数多项式函数<math>\epsilon(x)</math>。{{notetag|因为数可以看作是度数为0的多项式函数，“可忽略函数”其实就是“函数值无穷小”在概念上的一个广义定义。}}

:'''（可忽略函数）''' 一个连续函数<math>\mu(x)</math>''可忽略''，当对任意足够大的正实数<math>x</math>，对任意正多项式<math>poly(x)=\frac{1}{\epsilon(x)}>0</math>，有
::<math>|\mu(x)|<\epsilon(x)=\frac{1}{poly(x)}</math>。

在基于[[計算複雜性理論]]的现代[[密码学]]中，一个安全技术是数学上可证明安全（provably secure）的意思通常是，此安全技术的失败{{notetag|比如在[[多项式时间]]内将[[单向函数]]逆反，或在[[多项式时间]]内将密码[[随机数]]发生器产生的数和真正随机数区别开来}}的[[概率]]是关于密钥长度<math>x=n</math>的一个''可忽略函数''（参见[[公钥密码学]]）。因为密钥长度<math>n</math>肯定是自然数，这就是为什么开篇的定义把定义域改为自然数域的原因。{{notetag|不过，此关于可忽略函数的数学定义从未规定函数输入<math>x</math>必须是密钥长度<math>n</math>。实际上在具体分析中，<math>x</math>可以是任何事先规定好的系统的某个参数，然后可以通过数学上的分析揭示一些并不显而易见的复杂系统的行为。}}

==注释==
{{notefoot}}

== 参考 ==
{{Reflist}}
* {{cite book | last = Goldreich | first = Oded | date = 2001 | title = Foundations of Cryptography: Volume 1, Basic Tools | publisher = Cambridge University Press | isbn = 0-521-79172-3 | url = http://www.wisdom.weizmann.ac.il/~oded/frag.html | access-date = 2007-03-02 | archive-date = 2020-08-11 | archive-url = https://web.archive.org/web/20200811120817/http://www.wisdom.weizmann.ac.il/~oded/frag.html | dead-url = no }}
* {{cite book| first = Michael | last = Sipser | authorlink = Michael Sipser | date = 1997 | title = Introduction to the Theory of Computation | url = https://archive.org/details/introductiontoth00sips | publisher = PWS Publishing | isbn = 0-534-94728-X | chapter = Section 10.6.3: One-way functions | pages = [https://archive.org/details/introductiontoth00sips/page/374 374]–376 }}
* {{cite book| first = Christos | last = Papadimitriou | authorlink = Christos Papadimitriou | date = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1 | chapter = Section 12.1: One-way functions | pages = 279–298 }}
* {{cite book | first = Jean François | last = Colombeau | authorlink = Jean François Colombeau | date = 1984 | title = New Generalized Functions and Multiplication of Distributions | publisher = Mathematics Studies 84, North Holland | isbn = 0-444-86830-5}}
* {{cite paper | first = Mihir | last = Bellare | date = 1997 | citeseerx = 10.1.1.43.7900 | title = A Note on Negligible Functions | publisher = Dept. of Computer Science & Engineering University of California at San Diego }}

[[Category:数学分析]]
[[Category:各类函数]]