線形加速定理

3行要約

1. 計算複雑性理論において、アルゴリズムの実行時間を定数倍短縮できるという定理。
2. チューリングマシンのテープ記号数を増やすことで、計算ステップを減らせる。
3. 計算量の理論的な限界を議論する際に用いられる、基礎的な成果である。