線形加速定理
計算複雑性理論における線形加速定理（せんけいかそくていり、英: linear speedup theorem）とは、与えられたチューリング機械に対して、同じ問題を解くより高速なチューリング機械の存在を述べる定理である。より正確に述べると次の通りである。任意の正の定数 c と時間量 f(n) で言語を決定するチューリング機械 M に対して、M と同じ言語を決定するチューリング機械 M' で時間量が高々 cf(n) + n + 2 であるようなものが存在する。[1]
証明[編集]
ここでは c = 1 / 2 の場合の証明の概略を述べる。いま M を時間量 f(n) で言語を決定するチューリング機械、k をテープ記号の個数、s を状態数とする。 M を模倣する新しいチューリング機械 M' を次のように構成する。M' のテープ記号の個数は k3 とし、各テープ記号は M の3つのテープ記号のチャンクを表すものと考える。M' のテープは M のテープを次のように圧縮して表現する。 M' の i 番目のセルは、M の 2i-1, 2i, 2i+1 番目のセルを表現する（これらブロックは重なりを持つことに注意）。
M のヘッドが現在のチャンクから隣のチャンクに移動するまでの M の状態遷移は、 M' の1ステップで模倣できる。というのも M のヘッドがひとつのチャンクに留まり続けている間に取りうる状態遷移は繰り返しを除けば高々 sk3 だからである。このようにして M の複数ステップを M' の1ステップで模倣できた。
各チャンクは重なりを持つので重なりあった部分で矛盾した記号が現れうる。この場合はヘッド位置に最も近いチャンクが正しい。ヘッドがあるチャンクから次のチャンクに移動したときは、もとのチャンクの重なりあった部分のシンボルをチューリング機械の状態で一時的に記憶しておき、記号の不整合が発生したら正しい記号をコピーしてやればよい。
この構成は M' の計算の1ステップが少なくとも M の計算の2ステップに対応することを要請する。したがって M' は入力を圧縮表現に変換する線形のステップ数を除けば f(n)/2 ステップで M の実行を模倣する。
この証明は容易に全ての c > 0 に一般化できる。それにはチャンクの大きさを十分に大きく取ればよい。同様の方法で時間量を空間量に置き換えたものが証明できる。これはテープ圧縮定理として知られる。
関連項目[編集]
参考文献[編集]
- ^ Christos Papadimitriou (1994). “2.4. Linear speedup”. Computational Complexity. Addison Wesley