薩維奇定理

薩維奇定理（英語：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
  
• 直接規定定理結論中的 即可。
  

參見

• 空間層次定理