薩維奇定理

薩維奇定理（英語：Savitch's theorem）是計算複雜性理論中的一個定理，由沃爾特·薩維奇於1970年證明。定理的結論為對於任何函數$f(n)$滿足$f(n)\geq \log n$，下列關係成立：

${\text{NSPACE}}\left(f\left(n\right)\right)\subseteq {\text{DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right).$

亦即，如果一台非確定型圖靈機能夠利用$f(n)$空間解決某個問題，那麼一台確定型圖靈機能夠在至多$f^{2}(n)$空間解決相同的問題。儘管非確定性的引入能夠在時間上帶來指數的提升，但是，這種引入對於空間而言作用有限。

證明

薩維奇定理的證明是構造性的。證明過程為設計一個針對有向圖連通性問題的算法（其它問題可以通過圖靈機的格局圖歸約到此問題）。有向圖連通問題可以簡述為對於一個有向圖和給定的兩個頂點s和t，是否存在從s到t的有向路徑。對於n個頂點，存在一個算法在${\mbox{O}}\left((\log {n})^{2}\right)$空間內解決這一問題。這一算法的基本思路是利用遞歸解決一個更一般化的問題：檢查是否存在從s到t的一條至多包含k條邊的有向路徑，k是遞歸的輸入參數。原始的有向圖連通問題當$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

這一遞歸過程的遞歸深度為$O(\log n)$層，每層需要${\mbox{O}}(\log {n})$位來存儲該層的函數參數和局部變量。因此，算法的總空間複雜度為${\mbox{O}}\left((\log {n})^{2}\right)$。上述算法儘管是使用高級語言進行描述，然而，相同的算法使用圖靈機實現時所需要的空間上界在漸近意義下是等同的。

由於有向圖連通性問題為NL完全問題，因而任意NL中的語言都在複雜度類${\text{DSPACE}}\left(\left(\log n\right)^{2}\right)$中（這一複雜度類也常常被寫作L²）.

推論

從薩維奇定理可以得到許多重要的推論：

• PSPACE = NPSPACE
  • 得出這一結論因為多項式函數的平方仍然是一個多項式。儘管對於空間，確定性類與非確定性類相等，但是一般認為，對於時間的確定性類P和非確定性類NP，這種關係不成立，儘管這一假設尚是一個懸而未決的問題。
• NL ⊆ L²
  • 直接規定定理結論中的$f(n)=\log n$即可。

參見

• 空間層次定理

參考資料

• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X.  Section 8.1: Savitch's Theorem, pp.279–281.
• Christos Papadimitriou. Computational Complexity 1st edition. Addison Wesley. 1993. ISBN 0-201-53082-1.  引文格式1維護：冗餘文本 (link) 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 Lipton, Savitch’s Theorem （頁面存檔備份，存於互聯網檔案館）. 這篇文章從歷史的角度介紹了這一定理的證明是如何被發現的.