加速定理

計算複雑性理論における加速定理（かそくていり、英: speedup theorem）は、ある問題を解く算法に対し、同じ問題をより早く解く算法（また一般に、使用する資源がより少ない算法）の存在を示す定理である。

例として回文（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))}$ で実行できることを示した定理である。

理論 ${\displaystyle T}$ とその拡大理論 ${\displaystyle S}$ について「${\displaystyle T}$ において証明可能な論理式で ${\displaystyle S}$ においてはより簡単に証明できるものが存在する」という形の定理は、計算複雑性に関する加速定理の類比として、同じく加速定理と呼ばれる。その代表的なものとしてはゲーデルの加速定理がある。これら異なるタイプの加速定理の間には或る種の対応が存在する。例えば、ブラムの加速定理の変種であるハルトマニスの加速定理を用いてゲーデルの加速定理が証明できることが知られている。^[1]また、エーレンフォイヒト・ミッシェルスキーの加速定理は、帰納的可算集合の加速可能性に関するある事実を用いて証明できる。^[2]

• 計算複雑性理論

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

• 表示
• 編集