ブラムの加速定理

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

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

加速定理

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

$f(x,\Phi _{j}(x))\leq \Phi _{i}(x)$

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

関連項目

• ゲーデルの加速定理
• 加速定理

参考文献

• Blum, Manuel (1967). “A Machine-Independent Theory of the Complexity of Recursive Functions”. Journal of the ACM 14 (2): 322–336. doi:10.1145/321386.321395. ISSN 00045411. 
• 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. 13–29.

外部リンク

• Weisstein, Eric W. "Blum's Speed-Up Theorem". mathworld.wolfram.com (英語).