萨维奇定理
萨维奇定理(英語:)是计算复杂性理论中的一个定理,由沃尔特·萨维奇(Walter Savitch)于1970年证明。定理的结论为对于任何函数满足,下列关系成立:
亦即,如果一台非确定型图灵机能够利用空间解决某个问题,那么一台确定型图灵机能够在至多空间解决相同的问题。尽管非确定性的引入能够在时间上带来指数的提升,但是,这种引入对于空间而言作用有限。
证明
萨维奇定理的证明是构造性的。证明过程为设计一个针对有向图连通性问题的算法(其它问题可以通过图灵机的格局图归约到此问题)。有向图连通问题可以简述为对于一个有向图和给定的两个顶点s和t,是否存在从s到t的有向路径。对于n个顶点,存在一个算法在空间内解决这一问题。这一算法的基本思路是利用递归解决一个更一般化的问题:检查是否存在从s到t的一条至多包含k条边的有向路径,k是递归的输入参数。原始的有向图连通问题当时与此问题等价。为了测试是否存在一条从s到t的长度为k的有向边,可以测试是否存在一条从s到t的以u为中点的有向边。如果存在,那么对从s到u和从u到t递归此算法。
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中的语言都在复杂度类中(这一复杂度类也常常被写作L2).
推论
从萨维奇定理可以得到许多重要的推论:
参见
- 空间层次定理
参考资料
- Michael Sipser. . PWS Publishing. 1997. ISBN 0-534-94728-X. Section 8.1: Savitch's Theorem, pp.279–281.
- Christos Papadimitriou. 1st edition. Addison Wesley. 1993. ISBN 0-201-53082-1. Pages 149–150 of section 7.3: The Reachability Method.
- W.J.Savitch, "Relationship between nondeterministic and deterministic tape classes", Journal of Computer and System Sciences, 4, pp 177-192, 1970
外部链接
- Lance Fortnow, Foundations of Complexity, Lesson 18: Savitch's Theorem 页面存档备份,存于. 访问于2009年9月9日.
- Richard J. Lipton, Savitch’s Theorem 页面存档备份,存于. 这篇文章从历史的角度介绍了这一定理的证明是如何被发现的.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.