ブラムの加速定理とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > ブラムの加速定理の意味・解説 

ブラムの加速定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2015/05/01 09:18 UTC 版)

ブラムの加速定理(ぶらむのかそくていり、: Blum's speedup theorem)は計算複雑性理論における計算可能関数の複雑性に関する基本定理であり、1967年にマヌエル・ブラムによって示された。

計算可能関数は無限個の相異なるプログラム表現を持つ。アルゴリズムの理論はそのようなプログラムから与えられた複雑性測度に対して最小となるプログラム(最適なプログラム)を探る。ブラムの加速定理は、いかなる複雑性測度に対しても最適なプログラムの存在しないような関数が複雑性測度に応じて存在することを述べる。これはまた任意の関数に対してその計算複雑性を割り当てる方法、つまり任意の関数 f に対して f を表現する最適なプログラムの複雑性を割り当てる方法が存在しないことを示している。このことは特定の具体的な関数について最適なプログラムの複雑性を探すことができないということを意味しない。

加速定理

複雑性測度 と2変数全域再帰的関数 を所与とする。このとき全域再帰的関数 (これはブール値関数にできる)が存在して、 の任意の指標 に対して、 の指標 が存在して、ほとんど全ての に対して次が成り立つ:

加速関数と呼ばれる。 これを必要なだけ急増加な関数とすれば、 プログラム を与える毎にそれよりも必要なだけ高速なプログラム が得られる。例えば とすれば の複雑性は である。

関連項目

参考文献

外部リンク




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「ブラムの加速定理」の関連用語

ブラムの加速定理のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



ブラムの加速定理のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのブラムの加速定理 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS