薩維奇定理

薩維奇定理(英語:Savitch's theorem)是計算複雜性理論中的一個定理,由沃爾特·薩維奇英語Walter Savitch於1970年證明。定理的結論為對於任何函數滿足,下列關係成立:

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

證明

薩維奇定理的證明是構造性的。證明過程為設計一個針對有向圖連通性問題的算法(其它問題可以通過圖靈機的格局圖歸約到此問題)。有向圖連通問題可以簡述為對於一個有向圖和給定的兩個頂點st,是否存在從st的有向路徑。對於n頂點,存在一個算法在 空間內解決這一問題。這一算法的基本思路是利用遞歸解決一個更一般化的問題:檢查是否存在從st的一條至多包含k條邊的有向路徑,k是遞歸的輸入參數。原始的有向圖連通問題當 時與此問題等價。為了測試是否存在一條從st的長度為k有向邊,可以測試是否存在一條從st的以u為中點的有向邊。如果存在,那麼對從su和從ut遞歸此算法。

偽代碼表示如下(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中的語言都在複雜度類 中(這一複雜度類也常常被寫作L2).

推論

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

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

參見

參考資料

外部連結