線形加速定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/04/30 09:02 UTC 版)
計算複雑性理論における線形加速定理（せんけいかそくていり、英: linear speedup theorem）とは、与えられたチューリング機械に対して、同じ問題を解くより高速なチューリング機械の存在を述べる定理である。より正確に述べると次の通りである。任意の正の定数 c と時間量 f(n) で言語を決定するチューリング機械 M に対して、M と同じ言語を決定するチューリング機械 M' で時間量が高々 cf(n) + n + 2 であるようなものが存在する。[1]
- ^ Christos Papadimitriou (1994). “2.4. Linear speedup”. Computational Complexity. Addison Wesley.
[続きの解説]
「線形加速定理」の続きの解説一覧
- 1 線形加速定理とは
- 2 線形加速定理の概要
- 線形加速定理のページへのリンク
