English Dictionary

Blum's speedup theorem

固有名詞

(computing theory) A fundamental theorem about the complexity of computable functions, stating that for any complexity measure there are computable functions that are not optimal with respect to that measure.

日本語の意味

（計算理論）基本的な定理の一つで、任意の複雑性測度に対し、その測度で最適な計算可能関数が存在しない、すなわち常にさらなる高速化が可能な計算可能関数が存在することを示している。

Blum's speedup theorem shows that for every reasonable complexity measure there are computable functions that lack a single optimal program, because one can always find programs with progressively better resource bounds.

ブルームのスピードアップ定理は、任意の妥当な複雑性測度に対して単一の最良のプログラムを持たない計算可能関数が存在することを示しており、常に次々とより良い資源上限を達成するプログラムを見つけることができるためです。

意味（1）

(computing theory) A fundamental theorem about the complexity of computable functions, stating that for any complexity measure there are computable functions that are not optimal with respect to that measure.