無視可能函数
「無視可能」という概念は sound models of analysis にまで遡ることができる。 ニュートンやライプニッツの時代(1680年代)には連続性や無限小の概念が重要な意味を持つようになっていたが、これらの概念は後の1810年代になるまではきちんと定義されたものではなかった。解析学において「連続性」の意味のある厳密な定義が初めて成されるのは、ベルナルト・ボルツァーノが1817年に著した『連続性の現代的定義』においてである。その後、コーシー、ワイエルシュトラスおよびハイネらも以下のような定義を与えている。ここでは数は全て実数全体の成す集合 R に属するものとする。
計算量に基づく現代暗号理論では、セキュリティ方式が証明可能な安全性を持つとは、入力項 x を長さ n の暗号鍵とするとき、セキュリティ失敗(例えば一方向函数が覆されたり、暗号論的強擬似乱数ビットが真のビットと峻別されたり)の可能性が「無視できる」ことをいう。これを適用するためには、鍵長 n は自然数でないといけないので、冒頭の定義における x は自然数としている。
もちろん、無視可能函数の一般概念では系の入力変数 x は何も鍵長 n である必要はないのであって、実際 x は事前に与えられた系の任意の計量としてよく、無視可能函数についての解析学は、こういった系のある種の隠れた解析学的振る舞いを記述するものになる。
多項式の逆数による定式化は、計算論的有界性が多項式時間に従って定義されるのと同じ理由で利用される。これは閉包性質を持つから漸近的な設定において御しやすい。例えば仮に、無視できる可能性しかないセキュリティ条件に反して攻撃が成功したとして、攻撃回数が多項式オーダーで繰り返されたならば、攻撃が全般にわたって成功する可能性はそれでもまだ無視できる。実用上はもっと具体的な函数が求められ、それによって相手の成功可能性を低く抑えたり、その可能性が適当な閾値(2 など)を超えない程度に十分に長いセキュリティー変数を選んだりする。