計算複雑性理論における加速定理（かそくていり、）は、ある問題を解く算法に対し、同じ問題をより早く解く算法（また一般に、より少ない資源しか使用しない算法）の存在を示す定理である。例として回文（palindrome）を受理する1-テープチューリング機械を考える。次のアルゴリズムは formula_1 の時間計算量を持つ。同じ問題を formula_2 で解く次のような2-テープチューリング機械が考えられる。なおこの計算量は最適である。回文であるか否かは少なくともその文字列の長さ分はテープ上を走査しないと判定できない。チューリング機械が入力に対してその長さ未満の時間で受理（または拒否）したなら、その入力の末尾にいかなる文字列を付け加えても受理（または拒否）する。ところが、いかなる文字列も末尾に適当な文字列を付け加えることで回文にも非-回文にもできるので、したがってこのチューリング機械は回文を受理しない。チューリング機械に関する線形加速定理は、ある時間［ないし空間］計算量 formula_3 のチューリング機械を与えると、同じ問題を解く時間［ないし空間］計算量 formula_4 のチューリング機械が存在することを示した定理である（ただし formula_5 は入力の大きさ、formula_6 は正の定数）。ブラムの加速定理は、時間計算量 formula_7 の算法があれば、時間計算量 formula_8 の算法も存在するような問題の存在を示す。この結果はブラムの加速定理の特別な場合である。この定理は時間計算量に限らずブラムの公理を満たす任意の複雑性の測り方に対して成り立つ。加速の度合いも計算可能関数の範囲で自由に指定できる。上の主張は複雑性測度として時間計算量を取り、加速関数を formula_9 とした場合に相当する。量子コンピュータに関する2次関数的加速定理は、決定性コンピュータが時間計算量 formula_10 で検索が実行できるなら、量子コンピュータなら同一の検索が時間計算量 formula_11 で実行できることを示した定理である。理論 formula_12 とその拡大理論 formula_13 について「formula_12 において証明可能な論理式で formula_13 においてはより簡単に証明できるものが存在する」という形の定理は、計算複雑性に関する加速定理の類比として、同じく加速定理と呼ばれる。その代表的なものとしてはゲーデルの加速定理がある。

出典:wikipedia