定律与定理 › 定理
萨维奇定理
Savitch's theorem
theorem that problems solvable nondeterministically in space S may be solved deterministically in space O(S²)
萨维奇定理 是计算复杂性理论中的一个定理，由沃尔特·萨维奇于1970年证明。定理的结论为对于任何函数满足，下列关系成立：
摘自维基百科「萨维奇定理」，CC BY-SA 4.0
中文维基百科英文维基百科Wikidata
格物