3.4.2 萨维奇定理（Savitch's Theorem）：确定性与非确定性空间的等价性

文档摘要

3.4.2 萨维奇定理（Savitch's Theorem）：确定性与非确定性空间的等价性 3.4.2 萨维奇定理（Savitch's Theorem）：确定性与非确定性空间的等价性想象一下，你正站在计算理论的十字路口，一边是确定性图灵机（DTM），它像一位严谨的工程师，一步一个脚印地探索路径；另一边是非确定性图灵机（NTM），它像一位魔法师，能瞬间分支出无数可能性，瞬间抵达答案。问题是，当我们限制它们的“工作台”空间时——也就是空间复杂度——这两位“选手”谁更强大？萨维奇定理（Savitch's Theorem）给出了震撼答案：NTM的空间优势其实是表象，在空间$s(n)$下，NTM的计算能力完全可以用DTM以$s(n)^2$空间模拟。