圧縮定理

3行要約

1. 計算複雑性理論において、計算資源を増やすことで解ける問題が確実に増えることを示す定理。
2. 特定の時間や空間の制約内で計算可能な関数のクラスが存在することを保証する。
3. アルゴリズムの効率性の限界を論じる際の、理論的な基礎となっている。