萨维奇定理 _生活百科

萨维奇定理萨维奇定理（英语：Savitch's theorem）是计算複杂性理论中的一个定理，由沃尔特·萨维奇（Walter Savitch）于1970年证明。
基本介绍中文名：萨维奇定理
外文名：Savitch's theorem
证明萨维奇定理的证明是构造性的。证明过程为设计一个针对有向图连通性问题的算法（其它问题可以通过图灵机的格局图归约到此问题）。有向图连通问题可以简述为对于一个有向图和给定的两个顶点s和t，是否存在从s到t的有向路径。对于n个顶点，存在一个算法在{\displaystyle {\mbox{O}}\left((\log {n})^{2}\right)}空间内解决这一问题。这一算法的基本思路是利用递归解决一个更一般化的问题：检查是否存在从s到t的一条至多包含k条边的有向路径，k是递归的输入参数。原始的有向图连通问题当{\displaystyle k=n}时与此问题等价。为了测试是否存在一条从s到t的长度为k的有向边，可以测试是否存在一条从s到t的以u为中点的有向边。如果存在，那幺对从s到u和从u到t递归此算法。用伪代码表示如下（Python语法）：【萨维奇定理】def k-edge-path(s,t,k): if k == 0: return s == t else if k == 1: return (s,t) in edges else for u in vertices: if k-edge-path(s,u,?k/2?) and k-edge-path(u,t,?k/2?): return true return false这一递归过程的递归深度为

文章插图
层，每层需要

文章插图
位来存储该层的函式参数和局部变数。因此，算法的总空间複杂度为

文章插图
。上述算法儘管是使用高级语言进行描述，然而，相同的算法使用图灵机实现时所需要的空间上界在渐近意义下是等同的。由于有向图连通性问题为NL完全问题，因而任意NL中的语言都在複杂度类

文章插图
中（这一複杂度类也常常被写作L）.推论从萨维奇定理可以得到许多重要的推论：PSPACE=NPSPACE
得出这一结论因为多项式函式的平方仍然是一个多项式。儘管对于空间，确定性类与非确定性类相等，但是一般认为，对于时间的确定性类P和非确定性类NP，这种关係不成立，儘管这一假设尚是一个悬而未决的问题。
NL?L
直接规定定理结论中的即可。

文章插图
参见空间层次定理