サヴィッチの定理

3行要約

1. 計算複雑性理論において、決定性空間と非決定性空間の関係を示す定理。
2. 非決定性チューリングマシンで解ける問題は、その2乗の空間があれば決定性マシンでも解ける。
3. 空間計算量に関しては決定性と非決定性の差が限定的であることを示す重要な結果である。