ブラムの加速定理

ブラムの加速定理（ぶらむのかそくていり、）は計算複雑性理論における計算可能関数の複雑性に関する基本定理であり、1967年にマヌエル・ブラムによって示された。
計算可能関数は無限個の相異なるプログラム表現を持つ。アルゴリズムの理論はそのようなプログラムから与えられた複雑性測度に対して最小となるプログラム（最適なプログラム）を探る。ブラムの加速定理は、いかなる複雑性測度に対しても最適なプログラムの存在しないような関数が複雑性測度に応じて存在することを述べる。これはまた任意の関数に対して"その"計算複雑性を割り当てる方法、つまり任意の関数 "f" に対して "f" を表現する最適なプログラムの複雑性を割り当てる方法が存在しないことを示している。このことは特定の具体的な関数について最適なプログラムの複雑性を探すことができないということを意味しない。
加速定理.
複雑性測度 formula_1 と2変数全域再帰的関数 formula_2 を所与とする。このとき全域再帰的関数 formula_3 （これはブール値関数にできる）が存在して、formula_3 の任意の指標 formula_5 に対して、formula_3 の指標 formula_7 が存在して、ほとんど全ての formula_8 に対して次が成り立つ：
formula_2 は加速関数と呼ばれる。 これを必要なだけ急増加な関数とすれば、 プログラム formula_5 を与える毎にそれよりも必要なだけ高速なプログラム formula_7 が得られる。例えば formula_13 とすれば formula_7 の複雑性は formula_15 である。