圧倒的

デジタル大辞泉

あっとう‐てき〔アツタウ‐〕【圧倒的】

読み方：あっとうてき

［形動］他より非常に勝っているさま。「—に強い」「—な支持を得る」

日本語活用形辞書

圧倒的

読み方：あっとうてき

名詞「圧倒」に、接尾辞「的」がついたもの。

» 「圧倒」の意味を調べる

日本語活用形辞書はプログラムで機械的に活用形や説明を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。

ウィキペディア

無視可能函数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2013/07/26 11:22 UTC 版)

数学における無視可能函数（むしかのうかんすう、英: negligible function）は、極限においていかなる多項式よりも非常に緩やかな増加をするような函数である。

定義

実数列 μ: N → R は、任意の正整数 c に対して適当な整数 N_c を選べば、x > N_c なる全ての x について

が成り立つようにできるとき、「無視できる」という。あるいは同じことだが、次のように定義してもよい。すなわち、実数列 μ: N → R が「無視できる」とは、任意の正値多項式 poly(•) に対して適当な自然数 N_poly を選べば、x > N_poly なる全ての x に対して

が成り立つようにできることをいう。

歴史

「無視可能」という概念は sound models of analysis にまで遡ることができる。 ニュートンやライプニッツの時代（1680年代）には連続性や無限小の概念が重要な意味を持つようになっていたが、これらの概念は後の1810年代になるまではきちんと定義されたものではなかった。解析学において「連続性」の意味のある厳密な定義が初めて成されるのは、ベルナルト・ボルツァーノが1817年に著した『連続性の現代的定義』においてである。その後、コーシー、ワイエルシュトラスおよびハイネらも以下のような定義を与えている。ここでは数は全て実数全体の成す集合 R に属するものとする。

連続函数

函数 f: R → R が点 x = x₀ において連続であるとは、いかなる正の数 ε > 0 に対しても正の数 δ > 0 を適当に選べば、|x − x₀| < δ ならば |f(x) − f(x₀)| < ε とできることをいう。

この古典的な連続性の定義を適当に書き換えれば、無視可能性の定義に書き直すことができる。まず、x₀ = ∞ において f(x₀) = 0 となる場合を考える。ここで「無限小」の概念を定義する必要が生じる。

無限小函数

連続函数 μ: R → R が（x を無限大に飛ばす極限で）無限小であるとは、あらゆる ε > 0 に対して適当な N_ε を選べば、x > N_ε なるとき常に |μ(x)| < ε とできることをいう。

引き続き、定義における ε > 0 を函数 1/x^c (c > 0) あるいは 1/poly(x)（poly(x) は正値多項式）に取り替えれば、先の無視可能函数の定義を得る。定数 ε > 0 も適当な定数多項式に対する 1/ploy(x) として書けるから、無視可能函数のクラスは（無限遠における）無限小函数のクラスの部分集合になっていることがわかる。

暗号理論

計算量に基づく現代暗号理論では、セキュリティ方式が証明可能な安全性を持つとは、入力項 x を長さ n の暗号鍵とするとき、セキュリティ失敗（例えば一方向函数が覆されたり、暗号論的強擬似乱数ビットが真のビットと峻別されたり）の可能性が「無視できる」ことをいう。これを適用するためには、鍵長 n は自然数でないといけないので、冒頭の定義における x は自然数としている。

もちろん、無視可能函数の一般概念では系の入力変数 x は何も鍵長 n である必要はないのであって、実際 x は事前に与えられた系の任意の計量としてよく、無視可能函数についての解析学は、こういった系のある種の隠れた解析学的振る舞いを記述するものになる。

多項式の逆数による定式化は、計算論的有界性が多項式時間に従って定義されるのと同じ理由で利用される。これは閉包性質を持つから漸近的な設定において御しやすい。例えば仮に、無視できる可能性しかないセキュリティ条件に反して攻撃が成功したとして、攻撃回数が多項式オーダーで繰り返されたならば、攻撃が全般にわたって成功する可能性はそれでもまだ無視できる。実用上はもっと具体的な函数が求められ、それによって相手の成功可能性を低く抑えたり、その可能性が適当な閾値（2⁻¹²⁸ など）を超えない程度に十分に長いセキュリティー変数を選んだりする。

参考文献

• Goldreich, Oded (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3. Fragments available at the author's web site.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 10.6.3: One-way functions, pp.374–376.
• Christos Papadimitriou (1993). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1.  Section 12.1: One-way functions, pp.279–298.
• Jean François Colombeau (1984). New Generalized Functions and Multiplication of Distributions. Mathematics Studies 84, North Holland. ISBN 0-444-86830-5. 

関連項目

• 無視可能集合
• コロンボ代数
• 超準解析
• 多項式の増加に関するグロモフの定理
• 超準微分積分学

Weblio日本語例文用例辞書

「圧倒的」の例文・使い方・用例・文例

• その候補は圧倒的な票数で当選した
• 圧倒的大勝利
• 圧倒的多数
• …の大部分，圧倒的多数
• 彼らが圧倒的な力で６年連続の優勝を勝ち取りました
• 圧倒的な影響力を行使する
• 圧倒的な反響によって
• 私たちの軍隊は圧倒的ですね。
• 彼は圧倒的多数で当選した。
• 英語の語彙が圧倒的に不足している。
• 最新のマルチコアGPUは圧倒的な描画性能を誇ります。
• 現在取り組んでいる技術開発が完成すれば業界を圧倒的にリードできます。
• 彼らは圧倒的に優勢な敵と戦っていた。
• 世論調査の結果から、圧倒的多数の人がその法律を支持していることがわかる。
• 私たちの行動の圧倒的な部分は学んで身についたものだ。
• 議案は圧倒的多数で可決された。
• 圧倒的多数がその残酷な刑罰を廃止することに票を投じた。
• しかし、アメリカ同様日本も中流階級の平均的収入の人々が圧倒的多数を占める国なので、妻たちはメイドを雇わず、自分で何もかもに励む。
• 圧倒的な勝利.
• クリントン氏が圧倒的な得票差で当選した.