萨维奇定理 萨维奇定理英語Savitchs theorem是计算复杂性理论中的一个定理由沃尔特萨维奇英语Walter Savitch于年证明定理的结论为对于任何函数 f  n  displaystyle fn 满足 f  n   log  n displaystyle fngeq log n 下列关系成立 NSPACE  f  n    DSPACE   f  n      displaystyle textNSPACEleftfleftnrightrightsubseteq textDSPACEleftleftfleftnrightrightright 亦即如果一台非确定型图灵机能够利用 f  n  displaystyle fn 空间解决某个问题那么一台确定型图灵机能够在至多 f   n  displaystyle fn 空间解决相同的问题尽管非确定性的引入能够在时间上带来指数的提升但是这种引入对于空间而言作用有限