加速定理

例として回文（palindrome）を認識する1-テープチューリング機械を考える。次のアルゴリズムは ${\displaystyle O(n^{2})}$ の時間計算量を持つ。

1. 入力の左端の記号を読み取り空白記号を書き込む。このとき読み取った記号を記憶しておく。
2. 入力の右端までヘッドを動かして、記号を読み取る。このとき左側にあった記号と異なるなら拒否して停止する。さもなくば空白記号を書き込む。
3. 空白で埋まったら受理する。さもなくば(1)に戻る。（左端に戻るのは非効率であるから、左右を入れ替えて同じことを繰り返してもよいが、計算量のオーダーは変わらない。）

同じ問題を ${\displaystyle O(n)}$ で解く次のような2-テープチューリング機械が考えられる。

1. 入力を作業用テープにコピーする。
2. 入力用テープのヘッドを左端に、作業用テープのヘッドを右端に設定する。
3. 入力用テープの記号を読み取り、作業用テープの記号を読み取る。このとき異なる記号を読み取ったならば拒否して停止する。さもなくば入力用テープのヘッドを右に進め、作業用テープのヘッドを左に進める。
4. もし(3)において（同時に）空白を読み取ったならば受理して停止する。さもなくば(3)に戻る。

なおこの計算量は最適である。回文であるか否かは少なくともその文字列の長さ分はテープ上を走査しないと判定できない。チューリング機械が、ある入力に対してその長さ未満の時間で受理（または拒否）したとすると、その入力の末尾にいかなる文字列を付け加えても受理（または拒否）する。ところが、いかなる文字列も末尾に適当な文字列を付け加えることで回文にも非-回文にもできる。したがってこのチューリング機械は回文を認識しない。

チューリング機械に関する線形加速定理は、ある時間［ないし空間］計算量 ${\displaystyle f(n)}$ のチューリング機械を与えると、 同じ問題を解く時間［ないし空間］計算量 ${\displaystyle cf(n)}$ のチューリング機械が存在することを示した定理である（ただし ${\displaystyle n}$ は入力の大きさ、${\displaystyle c}$ は正の定数）。

ブラムの加速定理は、時間計算量 ${\displaystyle \mathrm {O} (f(n))}$ の算法があれば、時間計算量 ${\displaystyle \mathrm {O} (\log f(n))}$ の算法も存在するような問題の存在を示す。この結果はブラムの加速定理の特別な場合である。この定理は時間計算量に限らずブラムの公理を満たす任意の複雑性の測り方に対して成り立つ。加速の度合いも計算可能関数の範囲で自由に指定できる。上の主張は複雑性測度として時間計算量を取り、加速関数を ${\displaystyle r(x,y)=2^{y}}$ とした場合に相当する。

量子コンピュータに関する2次関数的加速定理は、決定性コンピュータが時間計算量 ${\displaystyle O(f(n))}$ で検索が実行できるなら、量子コンピュータなら同一の検索が時間計算量 ${\displaystyle O(\surd f(n))}$ で実行できることを示した定理である。