Savitch 定理

对于任何 $f:N\to R^+$ 的函数满足 $f(n)\ge\log n$，都有

$$\operatorname{NSPACE}(f(n)) \subseteq \operatorname{SPACE}\left(f^{2}(n)\right)$$

证明方法

转化为可生成性问题，即能否在 $t=2^{O(f(n))}$ 步骤内从开始组态变换到接受组态，然后用递归的方式来求解。