About: 線形加速定理

計算複雑性理論における線形加速定理（せんけいかそくていり、英: linear speedup theorem）とは、与えられたチューリング機械に対して、同じ問題を解くより高速なチューリング機械の存在を述べる定理である。より正確に述べると次の通りである。任意の正の定数 c と時間量 f(n) で言語を決定するチューリング機械 M に対して、M と同じ言語を決定するチューリング機械 M' で時間量が高々 cf(n) + n + 2 であるようなものが存在する。