ブラムの加速定理のソースを表示

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

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

== 加速定理 ==

複雑性測度 <math>(\varphi,\Phi)</math> と2変数全域再帰的関数 <math>f</math> を所与とする。このとき全域再帰的関数 <math>g</math> （これは[[ブール値関数]]にできる）が存在して、<math>g</math> の任意の[[ゲーデル数|指標]] <math>i</math> に対して、<math>g</math> の指標 <math>j</math> が存在して、[[ほとんど全ての]] <math>x</math> に対して次が成り立つ：
:<math>f(x, \Phi_j(x)) \leq \Phi_i(x) </math>

<math>f</math> は'''加速関数'''と呼ばれる。 これを必要なだけ'''急増加'''な関数とすれば、 プログラム <math>i</math> を与える毎にそれよりも必要なだけ'''高速'''なプログラム <math>j</math> が得られる。例えば <math>f(x, y) = 2^y </math> とすれば <math>j</math> の複雑性は <math>O(\log \Phi_i(x))</math> である。

== 関連項目 ==
* [[ゲーデルの加速定理]]
* [[加速定理]]

== 参考文献 ==
* {{cite journal|last1=Blum|first1=Manuel|title=A Machine-Independent Theory of the Complexity of Recursive Functions|journal=Journal of the ACM|volume=14|issue=2|year=1967|pages=322–336|issn=00045411|doi=10.1145/321386.321395}}
* Peter van Emde Boas, Ten years of speedup, Proceedings of MFCS (Jirí Becvár, ed.), Lecture Notes in Computer Science, vol. 32, Springer, 1975, pp.&nbsp;13–29.

== 外部リンク ==
* {{MathWorld|title=Blum's Speed-Up Theorem|urlname=BlumsSpeed-UpTheorem}}

{{デフォルトソート:ふらむのかそくていり}}
[[Category:計算複雑性理論の定理]]
[[Category:数学に関する記事]]