種々の加速定理とは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/04 01:50 UTC 版)

「加速定理」の記事における「種々の加速定理」の解説

チューリング機械に関する線形加速定理は、ある時間［ないし空間］計算量 f ( n ) {\displaystyle f(n)} のチューリング機械を与えると、同じ問題を解く時間［ないし空間］計算量 c f ( n ) {\displaystyle cf(n)} のチューリング機械が存在することを示した定理である（ただし n {\displaystyle n} は入力の大きさ、 c {\displaystyle c} は正の定数）。 ブラムの加速定理は、時間計算量 O ( f ( n ) ) {\displaystyle \mathrm {O} (f(n))} の算法があれば、時間計算量 O ( log ⁡ f ( n ) ) {\displaystyle \mathrm {O} (\log f(n))} の算法も存在するような問題の存在を示す。この結果はブラムの加速定理の特別な場合である。この定理は時間計算量に限らずブラムの公理を満たす任意の複雑性の測り方に対して成り立つ。加速の度合いも計算可能関数の範囲で自由に指定できる。上の主張は複雑性測度として時間計算量を取り、加速関数を r ( x , y ) = 2 y {\displaystyle r(x,y)=2^{y}} とした場合に相当する。 量子コンピュータに関する2次関数的加速定理は、決定性コンピュータが時間計算量 O ( f ( n ) ) {\displaystyle O(f(n))} で検索が実行できるなら、量子コンピュータなら同一の検索が時間計算量 O ( √ f ( n ) ) {\displaystyle O(\surd f(n))} で実行できることを示した定理である。

※この「種々の加速定理」の解説は、「加速定理」の解説の一部です。
「種々の加速定理」を含む「加速定理」の記事については、「加速定理」の概要を参照ください。