計算理論空間復(fù)雜

1、1計算理論2主要內(nèi)容主要內(nèi)容8.1 薩維奇定理薩維奇定理8.2 PSPACE 類類8.3 PSPACE 完全性完全性8.3.1 TQBF問題問題8.3.2 博弈的必勝策略博弈的必勝策略8.3.3 廣義地理學(xué)廣義地理學(xué)8.4 L 類類 NL 類類8.5 NL 完全性完全性8.6 NL 等于等于 coNL空間復(fù)雜度令令 M 是一個在所有輸入上都停機的確定型圖靈機。是一個在所有輸入上都停機的確定型圖靈機。M 的的空間復(fù)雜度空間復(fù)雜度是一個函數(shù)是一個函數(shù) f : NN，其中，其中 f (n) 是是 M 在任何長為在任何長為 n 的輸入上掃描帶方格的最大數(shù)的輸入上掃描帶方格的最大數(shù)。若若 M 的空間復(fù)雜

2、度為的空間復(fù)雜度為 f(n)，也稱，也稱 M 在空間在空間 f(n)內(nèi)運。內(nèi)運。如果如果 M 是對所有輸入是對所有輸入在所有分支上都停機在所有分支上都停機的的非確定型圖靈機非確定型圖靈機，則定義它的則定義它的空間復(fù)雜度空間復(fù)雜度 f (n) 為為 M 在任何長為在任何長為 n 的輸入上，在的輸入上，在任何計算分支上所掃描的帶方格的最大數(shù)任何計算分支上所掃描的帶方格的最大數(shù)。通常用漸進記法估計圖靈機的空間復(fù)雜度。通常用漸進記法估計圖靈機的空間復(fù)雜度。空間復(fù)雜性類令令 f : NR+是一個函數(shù)，是一個函數(shù)，空間復(fù)雜性類空間復(fù)雜性類 SPACE(f(n)和和 NSPACE(f(n)定義如下：定義如下

3、： SPACE(f(n) = L | L是被是被 O(f(n) 空間的空間的確定型圖靈機確定型圖靈機判定的語言判定的語言 NSPACE(f(n) = L | L是被是被 O(f(n) 空間的空間的非確定型圖靈機非確定型圖靈機判定的語言判定的語言 例8.3例例8.3 證明用線性空間算法能求解證明用線性空間算法能求解 SAT 問題。問題。M1 = “對輸入對輸入， 是布爾公式：是布爾公式：1) 對于對于 中中變量變量 x1 , , xm 的每個真值賦值：的每個真值賦值：2)計算計算 在該真值賦值下的值。在該真值賦值下的值。3) 若若 的值為的值為 1，則接受；否則拒絕。，則接受；否則拒絕。”顯然機

4、器顯然機器 M1 是在線性空間內(nèi)運行，因為每一次循環(huán)都是在線性空間內(nèi)運行，因為每一次循環(huán)都可以復(fù)可以復(fù)用帶子上的同一部分用帶子上的同一部分。該機器只需存儲當(dāng)前的真值賦值，這只。該機器只需存儲當(dāng)前的真值賦值，這只需需消耗消耗 O(m) 空間空間。因為變量數(shù)。因為變量數(shù) m 最多是輸入長度最多是輸入長度 n，所以該，所以該機器在空間機器在空間 O(n) 內(nèi)運行。內(nèi)運行。 例：語言的非確定性空間復(fù)雜性例例8.4 令令 ALLNFA | A 是一個是一個 NFA 且且 L(A) = * 首先給出非確定型線性空間算法來判定該語言的補首先給出非確定型線性空間算法來判定該語言的補 ALLNFA 。算法的思想

5、是利用算法的思想是利用非確定性猜測一個被非確定性猜測一個被 NFA 拒絕的字符串拒絕的字符串，然后，然后用線性空間用線性空間跟蹤該跟蹤該 NFA，看它在特定時刻處在什么狀態(tài)。，看它在特定時刻處在什么狀態(tài)。需要注意的是，此時還不知道該語言是否在需要注意的是，此時還不知道該語言是否在 NP 或或 coNP 中。中。N“對于輸入對于輸入 ，M 是是 NFA：1) 置標(biāo)記于置標(biāo)記于 NFA 的起始狀態(tài)。的起始狀態(tài)。2) 重復(fù)執(zhí)行下面的語句重復(fù)執(zhí)行下面的語句 2q 次次，這里，這里 q 是是 M 的狀態(tài)數(shù)。的狀態(tài)數(shù)。3) 非確定地選擇一個輸入符號并移動標(biāo)記到非確定地選擇一個輸入符號并移動標(biāo)記到 M 的相

6、的相 應(yīng)狀態(tài)應(yīng)狀態(tài)，來模擬讀取那個符號。，來模擬讀取那個符號。4) 如果步驟如果步驟 2 和和 3 表明表明 M 拒絕某些字符串，即如果在某一時刻所有標(biāo)拒絕某些字符串，即如果在某一時刻所有標(biāo)記都不落在記都不落在 M 的接受狀態(tài)上，則接受；否則拒絕。的接受狀態(tài)上，則接受；否則拒絕。”例：語言的非確定性空間復(fù)雜性7如果如果 M 拒絕某個字符串，則它必定拒絕一個長度不超過拒絕某個字符串，則它必定拒絕一個長度不超過 2q 的字符串，因的字符串，因為在任何被拒絕的更長的字符串中，上面算法中所描述的標(biāo)記的位置分布為在任何被拒絕的更長的字符串中，上面算法中所描述的標(biāo)記的位置分布必定重復(fù)出現(xiàn)。介于兩次重復(fù)出現(xiàn)

7、之間的那一段字符串可以刪去，從而得必定重復(fù)出現(xiàn)。介于兩次重復(fù)出現(xiàn)之間的那一段字符串可以刪去，從而得到更短的被拒絕的字符串。所以到更短的被拒絕的字符串。所以 N 可判定可判定 ALLNFA 的補。的補。該算法該算法僅需要的空間是用來存放標(biāo)記的位置和重復(fù)計數(shù)器僅需要的空間是用來存放標(biāo)記的位置和重復(fù)計數(shù)器，這在線性空間，這在線性空間就可以得到解決。因此，該算法在非確定的空間就可以得到解決。因此，該算法在非確定的空間 O(n) 內(nèi)運行。內(nèi)運行。薩維奇定理對于任何函數(shù)對于任何函數(shù) f : NR+ ，其中，其中 f(n) n，NSPACE( f(n) ) SPACE( f 2(n) )給定給定 NTM 的

8、兩個格局的兩個格局 c1 和和 c2，以及一個整數(shù)，以及一個整數(shù) t，要求判定該，要求判定該NTM 能否在能否在 t 步內(nèi)從步內(nèi)從 c1 變到變到 c2，稱該問題為，稱該問題為可產(chǎn)生性問題可產(chǎn)生性問題。如果如果 c1 是起始格局，是起始格局，c2 是接受格局，是接受格局，t 是非確定型機器所使用的最大步數(shù)，是非確定型機器所使用的最大步數(shù)，那么通過求解可產(chǎn)生問題，就能夠判斷機器是否接受輸入。那么通過求解可產(chǎn)生問題，就能夠判斷機器是否接受輸入。可以用一個可以用一個確定的遞歸算法確定的遞歸算法求解可產(chǎn)生問題。運算過程如下：求解可產(chǎn)生問題。運算過程如下：尋找一個中間格局尋找一個中間格局 cm，遞歸地檢

9、查，遞歸地檢查 c1 能否在能否在 t/2 步內(nèi)到達步內(nèi)到達 cm， cm 能否在能否在 t/2步內(nèi)到達步內(nèi)到達 c2，重復(fù)使用兩次遞歸檢查的空間可節(jié)省空間開銷重復(fù)使用兩次遞歸檢查的空間可節(jié)省空間開銷。遞歸的每一層需要遞歸的每一層需要 O(f(n)空間來存儲一個格局。遞歸的深度是空間來存儲一個格局。遞歸的深度是 log t，t 是非是非確定型機器在所有分支上可能消耗的最大時間，確定型機器在所有分支上可能消耗的最大時間，t=2O(f(n)，log t = O(f(n)。因此模擬過程需要因此模擬過程需要 O(f 2(n)。薩維奇定理的證明設(shè)設(shè) N 是在空間是在空間 f(n) 內(nèi)判定語言內(nèi)判定語言

10、A 的的 NTM。構(gòu)造一個判定構(gòu)造一個判定 A 的確定型的確定型 TM M。機器。機器 M 利用過程利用過程 CANYIELD，該過程，該過程檢查檢查 N 的一個格局能否在指定的步數(shù)內(nèi)產(chǎn)生另一個格局。的一個格局能否在指定的步數(shù)內(nèi)產(chǎn)生另一個格局。設(shè)設(shè) w 是輸入到是輸入到 N 的字符串。對于的字符串。對于 N 在在 w 上的格局上的格局 c1、c2 以及整數(shù)以及整數(shù) t，如果，如果從格局從格局 c1 出發(fā)，出發(fā)，N 有一系列非確定的選擇能使它在有一系列非確定的選擇能使它在 t 步內(nèi)進入格局步內(nèi)進入格局 c2 ，則，則CANYIELD (c1 , c2 , t) 輸出接受，否則，輸出接受，否則，C

11、ANYIELD 輸出拒絕。輸出拒絕。CANYIELD = “對輸入對輸入 c1, c2 和和 t：1) 若若 t=1，則直接檢查是否有，則直接檢查是否有 c1=c2 ，或者根據(jù)，或者根據(jù) N 的規(guī)則檢查的規(guī)則檢查 c1 能否能否在一步內(nèi)產(chǎn)生在一步內(nèi)產(chǎn)生c2。如果其中之一成立，則接受；如果兩種情況都不。如果其中之一成立，則接受；如果兩種情況都不成立，則拒絕。成立，則拒絕。2) 若若 t 1，則對于，則對于 N 在在 w上消耗空間上消耗空間 f(n) 的每一個格局的每一個格局cm：3) 運行運行 CANYIELD (c1 , cm , t /2 )。4) 運行運行 CANYIELD (cm , c

12、2 , t /2 )。5) 若第若第 3 和第和第 4 步都接受，則接受。步都接受，則接受。6) 若此時還沒有接受，則拒絕。若此時還沒有接受，則拒絕?！彼_維奇定理的證明現(xiàn)在定義現(xiàn)在定義 M 來模擬來模擬 N。首先修改。首先修改 N，當(dāng)它接受時，把帶子清空并把讀寫頭，當(dāng)它接受時，把帶子清空并把讀寫頭移到最左邊的單元，從而進入稱為移到最左邊的單元，從而進入稱為 caccept 的格局。的格局。令令 cstart 是是 N 在在 w 上的起始格局。選一個常數(shù)上的起始格局。選一個常數(shù) d，使得，使得 N 在在 f(n) 空間上的格空間上的格局?jǐn)?shù)不超過局?jǐn)?shù)不超過 2df(n) ，其中，其中 n 是是 w

13、 的長度。的長度。 2df(n) 是是 N 在所有分支上的運行時在所有分支上的運行時間的上界間的上界。M“對輸入對輸入 w：1) 輸出輸出 CANYIELD (cstart， caccept，2df(n) )的結(jié)果。的結(jié)果?！彼惴ㄋ惴?CANYIELD 顯然求解了可產(chǎn)生性問題，因此顯然求解了可產(chǎn)生性問題，因此 M 正確地模擬正確地模擬 N。下面需要分析下面需要分析 M，確信它在，確信它在 O(f(n)空間內(nèi)運行。空間內(nèi)運行。CANYIELD 在遞歸調(diào)用自己時，它都把所處的步驟號、在遞歸調(diào)用自己時，它都把所處的步驟號、c1、c2 和和 t 的都存的都存儲在棧中，所以遞歸調(diào)用時返回時能恢復(fù)這些值。

14、因此在遞歸的每一層需儲在棧中，所以遞歸調(diào)用時返回時能恢復(fù)這些值。因此在遞歸的每一層需要增加要增加 O(f(n) 空間?？臻g。此外，此外，遞歸的每一層把遞歸的每一層把 t 的值減小一半的值減小一半。開始時。開始時 t 等于等于2df(n) ，所以遞歸的，所以遞歸的深度是深度是 O(log 2df(n) 或或 O(f(n) ，因此共消耗空間是，因此共消耗空間是 O(f2(n) 。11主要內(nèi)容主要內(nèi)容8.1 薩維奇定理薩維奇定理8.2 PSPACE 類類8.3 PSPACE 完全性完全性8.3.1 TQBF 問題問題8.3.2 博弈的必勝策略博弈的必勝策略8.3.3 廣義地理學(xué)廣義地理學(xué)8.4 L

15、類類 NL 類類8.5 NL 完全性完全性8.6 NL 等于等于 coNLPSPACE 類PSPACE 是在是在確定型確定型圖靈機上、在圖靈機上、在多項式空間內(nèi)多項式空間內(nèi)可可判定的語言類。換言之，判定的語言類。換言之，PSPACE k SPACE(nk) PSPACE 類的非確定型版本類的非確定型版本 NPSPACE，可以類似地用，可以類似地用NSPACE 類來定義。類來定義。然而，任何多項式的平方仍是多項式，根據(jù)薩維奇定理，則然而，任何多項式的平方仍是多項式，根據(jù)薩維奇定理，則NPSPACE = PSPACE 。在例在例8.3和和8.4中，已經(jīng)說明了中，已經(jīng)說明了 SAT 屬于屬于 SPA

16、CE(n)， ALLNFA 屬屬于于 coNSPACE(n) ，而根據(jù)薩維奇定理，而根據(jù)薩維奇定理，確定型空間復(fù)雜度對確定型空間復(fù)雜度對補運算封閉補運算封閉，所以，所以 ALLNFA 也屬于也屬于 SPACE(n2) 。因此。因此 SAT 和和ALLNFA 這兩個語言都在這兩個語言都在 PSPACE 中中。PSPACE 類考察考察 PSPACE 與與 P 和和 NP 的關(guān)系。的關(guān)系。顯而易見，顯而易見，P PSPACE，因為，因為運行快的機器不可能消耗大量運行快的機器不可能消耗大量的空間的空間。更精確地說，當(dāng)。更精確地說，當(dāng) t(n)n 時，由于在每個計算步上時，由于在每個計算步上最多能訪問一

17、個新單元，因此，任何在時間最多能訪問一個新單元，因此，任何在時間 t(n) 內(nèi)運行的內(nèi)運行的機器最多能消耗機器最多能消耗 t(n) 的空間。的空間。類似地，類似地，NP NPSPACE ，所以，所以 NP PSPACE 。反過來，反過來，根據(jù)圖靈機的空間復(fù)雜性可以界定它的時間復(fù)雜性根據(jù)圖靈機的空間復(fù)雜性可以界定它的時間復(fù)雜性。對于對于 f (n )n ，通過簡單推廣引理，通過簡單推廣引理5.7 的證明可知，的證明可知，一個消耗一個消耗f(n) 空間的空間的 TM 至多有至多有 f(n)2O(f(n) 個不同的格局個不同的格局，也必定在，也必定在時間時間 f(n)2O(f(n) 內(nèi)運行，得出：內(nèi)

18、運行，得出： PSPACE EXPTIME = k TIME(2nk) P NP PSPACE=NPSPACE EXPTIME14主要內(nèi)容主要內(nèi)容8.1 薩維奇定理薩維奇定理8.2 PSPACE 類類8.3 PSPACE 完全性完全性8.3.1 TQBF 問題問題8.3.2 博弈的必勝策略博弈的必勝策略8.3.3 廣義地理學(xué)廣義地理學(xué)8.4 L 類類 NL 類類8.5 NL 完全性完全性8.6 NL 等于等于 coNLPSPACE 完全性語言語言 B 是是PSPACE完全的完全的。若它滿足下面兩個條件：。若它滿足下面兩個條件：1) B 屬于屬于 PSPACE。2) PSPACE中的每一個語言中

19、的每一個語言A多項式時間可歸約到多項式時間可歸約到B。若若 B 只滿足條件只滿足條件 2，則稱它為，則稱它為 PSPACE難的難的。TQBF 問題q 量詞量詞： 、 對于自然數(shù)，語句對于自然數(shù)，語句 x x+1x 為真。為真。 y y+y=y 為假。為假。q 轄域轄域：量詞的作用范圍。：量詞的作用范圍。q 前束范式前束范式： 形如形如 = Q1x1 Q2 x2 Qk xk B， Qi 為為 或或 q 量詞化布爾公式量詞化布爾公式：帶量詞的布爾公式（必須是前束范式）。：帶量詞的布爾公式（必須是前束范式）。q 全量詞化全量詞化：公式中的每個變量都出現(xiàn)在某一量詞的轄域中。：公式中的每個變量都出現(xiàn)在某

20、一量詞的轄域中。q TQBF 問題就是要判定一個全量詞化的布爾公式是真是假問題就是要判定一個全量詞化的布爾公式是真是假。TQBF=| 是真的全量詞化的布爾公式是真的全量詞化的布爾公式TQBF 問題TQBF 是是 PSPACE 完全的。完全的。q 證明思路證明思路 (1) 為了為了證明證明TQBF屬于屬于PSPACE，給出一個簡單的算法。該算法首先給變，給出一個簡單的算法。該算法首先給變量賦值，然后遞歸地計算公式在這些值下的真值。從這些信息中算法量賦值，然后遞歸地計算公式在這些值下的真值。從這些信息中算法就能確定原量化公式的真值。就能確定原量化公式的真值。(2) 為了為了證明證明PSPACE中的

21、每個語言中的每個語言A在多項式時間內(nèi)可歸約到在多項式時間內(nèi)可歸約到TQBF，從，從判定判定 A 的多項式空間界限圖靈機開始。然后給出多項式時間歸約，它的多項式空間界限圖靈機開始。然后給出多項式時間歸約，它把一個字符串映射為一個量詞化的布爾公式把一個字符串映射為一個量詞化的布爾公式， 模擬機器對這個輸入模擬機器對這個輸入的計算。的計算。公式為真的充分必要條件是機器接受公式為真的充分必要條件是機器接受。改用一種與薩維奇定理的證明相關(guān)的技術(shù)來構(gòu)造公式。該公式把畫面改用一種與薩維奇定理的證明相關(guān)的技術(shù)來構(gòu)造公式。該公式把畫面分成兩半，利用全稱量詞的功能，用公式的同一部分來代表每一半。分成兩半，利用全稱

22、量詞的功能，用公式的同一部分來代表每一半。結(jié)果產(chǎn)生短得多的公式。結(jié)果產(chǎn)生短得多的公式。TQBF 問題首先，給出一個判定首先，給出一個判定 TQBF 的多項式空間算法：的多項式空間算法：T “對輸入對輸入 ， 是一個全量詞化的布爾公式是一個全量詞化的布爾公式：1) 若若 不含量詞，則它是一個只有常數(shù)的表達式。計算不含量詞，則它是一個只有常數(shù)的表達式。計算 的值，若為的值，若為真，則接受；否則，拒絕。真，則接受；否則，拒絕。2) 若若 等于等于 x ，在，在 上遞歸地調(diào)用上遞歸地調(diào)用 T，首先用，首先用 0 替換替換 x，然后用，然后用 1 替換替換 x。只要有一個結(jié)果是接受只要有一個結(jié)果是接受，

23、則接受；否則，拒絕。，則接受；否則，拒絕。3) 若若 等于等于 x ，在，在 上遞歸地調(diào)用上遞歸地調(diào)用 T，首先用，首先用 0 替換替換 x，然后用，然后用 1 替換替換 x。若。若兩個結(jié)果都能接受兩個結(jié)果都能接受，則接受；否則，拒絕。，則接受；否則，拒絕。”算法算法 T 顯然判定顯然判定 TQBF 。空間復(fù)雜性：它遞歸的深度最多等于變量的個數(shù)。在每一層只需存儲一個空間復(fù)雜性：它遞歸的深度最多等于變量的個數(shù)。在每一層只需存儲一個變量的值，所以全部空間消耗是變量的值，所以全部空間消耗是 O(m)，其中，其中 m 是是 中出現(xiàn)的變量的個中出現(xiàn)的變量的個數(shù)。因此數(shù)。因此 T 在線性空間內(nèi)運行。在線性

24、空間內(nèi)運行。TQBF 問題下面，證明下面，證明 TQBF 是是 PSPACE 難的。難的。設(shè)設(shè) A 是一個由是一個由 TM M 在在 nk 空間內(nèi)判定的語言空間內(nèi)判定的語言，k 是某個常數(shù)。是某個常數(shù)。下面給出一個從下面給出一個從 A 到到 TQBF 的多項式時間歸約。該歸約的多項式時間歸約。該歸約把字符串把字符串 w 映射為一映射為一個量詞化的布爾公式個量詞化的布爾公式 ， 為為真當(dāng)且僅當(dāng)真當(dāng)且僅當(dāng) M 接受接受 w。為了說明怎樣構(gòu)造為了說明怎樣構(gòu)造 ，需解決一個更一般的問題。，需解決一個更一般的問題。利用兩個代表格局的變量利用兩個代表格局的變量集合集合 c1 和和 c2 及一個數(shù)及一個數(shù)

25、t 0，構(gòu)造一個公式，構(gòu)造一個公式 c1, c2 , t。如果把。如果把 c1 和和c2 賦為實際的賦為實際的格局，則該公式為真當(dāng)且僅當(dāng)格局，則該公式為真當(dāng)且僅當(dāng) M 能夠在能夠在最多最多 t 步內(nèi)從步內(nèi)從 c1到達到達 c2。然后，可以。然后，可以令令 是公式是公式 cstart , caccept, h，其中其中 h= 2df(n) ，d 是一個選取的常數(shù)，使得是一個選取的常數(shù)，使得 M 在長在長為為 n 的輸入上可能的格局?jǐn)?shù)不超過的輸入上可能的格局?jǐn)?shù)不超過 2df (n) 。這里，令。這里，令f(n)=nk。為了方便，假設(shè)。為了方便，假設(shè) t 是是 2 的冪。的冪。類似庫克類似庫克-列文

26、定理的證明，該公式對帶單元的內(nèi)容編碼。對應(yīng)于單元的可能列文定理的證明，該公式對帶單元的內(nèi)容編碼。對應(yīng)于單元的可能設(shè)置，每個單元有幾個相關(guān)的變量，每個帶符號和狀態(tài)有一個變量。每個格設(shè)置，每個單元有幾個相關(guān)的變量，每個帶符號和狀態(tài)有一個變量。每個格局有局有nk個單元，所以用個單元，所以用 O(nk) 個變量編碼。個變量編碼。TQBF問題若若 t=1，則容易構(gòu)造，則容易構(gòu)造 c1, c2 , t。設(shè)計公式，使之表達要么設(shè)計公式，使之表達要么 c1 等于等于 c2，要么，要么 c1能在能在 M 的一步內(nèi)變到的一步內(nèi)變到 c2 。為了表達相等性，使用一個布爾表達式來表示：為了表達相等性，使用一個布爾表達

27、式來表示：代表代表 c1 的每一個變量與代表的每一個變量與代表 c2 的相應(yīng)變量包含同樣的布爾值的相應(yīng)變量包含同樣的布爾值。為表達第二種可能性，采用庫克為表達第二種可能性，采用庫克-列文定理的證明中給出的技巧，構(gòu)造布爾表列文定理的證明中給出的技巧，構(gòu)造布爾表達式表示，達式表示，代表代表 c1 的每個三元組的值能正確產(chǎn)生相應(yīng)的的每個三元組的值能正確產(chǎn)生相應(yīng)的 c2 的三元組的值，的三元組的值，從而就能夠表達從而就能夠表達 c1 在在 M 的一步內(nèi)產(chǎn)生的一步內(nèi)產(chǎn)生 c2。若若 t1，遞歸的構(gòu)造遞歸的構(gòu)造 c1, c2 , t。作為預(yù)演。作為預(yù)演 ，先嘗試一種不太好的想法，然后再，先嘗試一種不太好的

28、想法，然后再修正它。令：修正它。令： c1, c2 , t = m1 c1, m1 , t/2 m1, c2 , t/2 符號符號 m1 表示表示 M 的一個格局。的一個格局。 m1是是 x1,.,xf 的縮寫，其中的縮寫，其中 l= O(nk) ， x1,., xf 是對是對 m1 編碼的變量。所以編碼的變量。所以 c1, c2 , t 的這個構(gòu)造的含義是：如果存在某個的這個構(gòu)造的含義是：如果存在某個中間格局中間格局 m1 ，使得，使得 M 在至多在至多 t/2 步內(nèi)從步內(nèi)從 c1 變到變到 m1，并且在至多，并且在至多 t/2步內(nèi)步內(nèi)從從 m1 變到變到 c2，那么，那么 M 就能在至多就

29、能在至多 t 步內(nèi)從步內(nèi)從 c1 變到變到 c2。然后再遞歸地構(gòu)造。然后再遞歸地構(gòu)造 c1, m1 , t/2 和和 m1, c2 , t/2 這兩個公式。這兩個公式。TQBF問題公式公式 c1, c2 , t 具有正確值。具有正確值。換言之，只要換言之，只要 M 能在能在 t 步內(nèi)從步內(nèi)從 c1 變到變到 c2 ，它就是，它就是 TRUE。然而，它太長了。構(gòu)造過程中涉及的遞歸的每一層都把。然而，它太長了。構(gòu)造過程中涉及的遞歸的每一層都把 t 的值減的值減小一半，卻把公式的長度增加了大約一倍，最后導(dǎo)致公式的長度大約是小一半，卻把公式的長度增加了大約一倍，最后導(dǎo)致公式的長度大約是 t，開始時開始

30、時 t= 2df(n)，所以這種方法結(jié)出的公式是指數(shù)長的。，所以這種方法結(jié)出的公式是指數(shù)長的。為了縮短公式的長度，除了使用為了縮短公式的長度，除了使用 量詞以外，再利用量詞以外，再利用 量詞。令量詞。令 c1, c2 , t = m1 (c3, c4) (c1, m1) ,(m1, c2) c3, c4 , t/2 新引入的變量代表格局新引入的變量代表格局 c3 和和 c4，它允許把兩個遞歸的子公式，它允許把兩個遞歸的子公式“折疊折疊”為一個為一個子公式，而保持原來的意思。通過寫成子公式，而保持原來的意思。通過寫成 (c3, c4 ) (c1, m1) ,(m1, c2)就指明了代表格局就指明

31、了代表格局 c3 和和 c4 的變量可以分別取的變量可以分別取 c1 和和 m1 的變量的值，或者的變量的值，或者 m1和和 c2 的變量的值，結(jié)果公式的變量的值，結(jié)果公式 c3, c4 , t/2 在兩種情況下都為真?？梢园呀Y(jié)構(gòu)在兩種情況下都為真?？梢园呀Y(jié)構(gòu) (c3, c4 ) (c1, m1) ,(m1, c2)替換為等價的結(jié)構(gòu)替換為等價的結(jié)構(gòu) x(x=y x=z) ，從而，從而得到語法正確的量化布爾公式。得到語法正確的量化布爾公式。為了計算公式個為了計算公式個 cstart， caccept,h 的長度，其中的長度，其中 h= 2df(n) ，注意到遞歸增加的那，注意到遞歸增加的那部分公

32、式的長度與格局的長度呈線性關(guān)系，所以長度是部分公式的長度與格局的長度呈線性關(guān)系，所以長度是O(f(n) 。遞歸的。遞歸的層數(shù)是層數(shù)是log2df(n) 或或 O(f(n) 。所以所得到的公式的長度是。所以所得到的公式的長度是O(f 2(n) 。博弈的必勝策略q 博奕論：每個游戲常有博奕論：每個游戲常有 2 個以上的參加者，他們個以上的參加者，他們(局中人局中人)在在游戲中都有自己的切身利益，每個局中人都有自己的可行行游戲中都有自己的切身利益，每個局中人都有自己的可行行動集供自己選擇，這種選擇毫無疑問地會影響到其他局中人動集供自己選擇，這種選擇毫無疑問地會影響到其他局中人的切身利益。游戲中各個局

33、中人理性地采取的切身利益。游戲中各個局中人理性地采取/選擇自己的策選擇自己的策略行為，使得在這種相互制約相互影響的依存關(guān)系中，盡可略行為，使得在這種相互制約相互影響的依存關(guān)系中，盡可能提高自己的利益所得，這正是游戲理論的關(guān)鍵所得。能提高自己的利益所得，這正是游戲理論的關(guān)鍵所得。q 要點：要點：博奕的各方都是理性的博奕的各方都是理性的各人的選擇都是為取得利益的最大化各人的選擇都是為取得利益的最大化囚徒困境q1950年，就職于蘭德公司的梅里爾年，就職于蘭德公司的梅里爾弗勒德（弗勒德（Merrill Flood）和梅爾文）和梅爾文德雷希爾（德雷希爾（Melvin Dresher）擬定出相關(guān)困境的理論

34、，后來由顧問艾）擬定出相關(guān)困境的理論，后來由顧問艾伯特伯特塔克（塔克（Albert Tucker）以囚徒方式闡述，并命名為）以囚徒方式闡述，并命名為“囚徒困境囚徒困境”。q經(jīng)典的囚徒困境如下：經(jīng)典的囚徒困境如下：兩個嫌犯被捕后被關(guān)在相互隔離的牢房中。他們面臨的選擇是：或者兩個嫌犯被捕后被關(guān)在相互隔離的牢房中。他們面臨的選擇是：或者坦白或者保持沉默（即不坦白）。他們被告知：坦白或者保持沉默（即不坦白）。他們被告知： 如果某個嫌疑犯坦白而其同伙不坦白，則坦白者可獲自由而拒不如果某個嫌疑犯坦白而其同伙不坦白，則坦白者可獲自由而拒不坦白者要被判坦白者要被判10年監(jiān)禁；年監(jiān)禁； 如果二人都坦白，則二人都

35、被判如果二人都坦白，則二人都被判5年監(jiān)禁；年監(jiān)禁； 如果二人都不坦白，則二人皆被判如果二人都不坦白，則二人皆被判1年監(jiān)禁。年監(jiān)禁。q上述情況我們亦可用一支付矩陣表示如下：上述情況我們亦可用一支付矩陣表示如下： 嫌疑犯乙嫌疑犯乙 坦白沉默坦白沉默 嫌疑犯甲坦白嫌疑犯甲坦白 -5, -50, -10 沉默沉默 -10, 0-1, -1 在這種情況下，兩個嫌犯將如何決策和選擇呢？在這種情況下，兩個嫌犯將如何決策和選擇呢？博弈的必勝策略q 博奕和量詞緊密相關(guān)博奕和量詞緊密相關(guān)q 一個量化語句一個量化語句一個博弈一個博弈作用：描述和解釋該語句的含義作用：描述和解釋該語句的含義q 一個博弈一個博弈一個量化

36、語句一個量化語句作用：理解該博弈的復(fù)雜性作用：理解該博弈的復(fù)雜性q 例：前束范式的量詞化布爾公式例：前束范式的量詞化布爾公式 = x1 x2 x3Qxk Q:/， -去掉量詞的公式去掉量詞的公式 與下面的博弈關(guān)聯(lián)：與下面的博弈關(guān)聯(lián)： 2 2名選手名選手A A, ,E E，輪流為，輪流為x1, x2 , x3 , , xk 選值選值博弈的必勝策略選手選手E所對所對應(yīng)的量詞應(yīng)的量詞選手選手A所對所對應(yīng)的量詞應(yīng)的量詞選手選手E取值取值選手選手A取值取值對變量進行對變量進行處理的語句處理的語句TRUE: E勝勝FALSE: A勝勝其中其中A對任意量詞約束的變量選值；對任意量詞約束的變量選值；E對存在量

37、詞約束的變量選值對存在量詞約束的變量選值例8.9 1 1= = x1 x2 x3(x1 x2 2) (x2 x3) (x2 x3)E確定的確定的變量值變量值A(chǔ)確定的確定的變量值變量值 設(shè)設(shè)E：x1=1;A：x2=0;E：x3=1; =1,E贏贏取值相反取值相反E必勝：必勝：設(shè)設(shè)E：x1=1/0;A：x2=0;E：x3=1/0; =0,A贏贏A必勝：必勝： 2 2= = x1 x2 x3(x1 x2 2) (x2 x3) (x2 x3) 必勝策略必勝策略一個選手有必勝策略，如果他在博弈雙方都下出最佳步驟時能贏一個選手有必勝策略，如果他在博弈雙方都下出最佳步驟時能贏博弈的必勝策略q 判定在與某具體

38、公式關(guān)聯(lián)的公式博弈中哪方有必勝策略的判定在與某具體公式關(guān)聯(lián)的公式博弈中哪方有必勝策略的問題是問題是 PSPACE 完全的。完全的。FORMULA-GAME= | 在與在與 關(guān)聯(lián)的公式博奕中選手關(guān)聯(lián)的公式博奕中選手E有必勝策略有必勝策略 博弈的必勝策略FARMULA-GAME 是是 PSPACE 完全的。完全的。要證要證FORMULA-GAME是是PSPACE完全的完全的FORMULA-GAME=TQBFFORMULA-GAME= | 是真的全量詞化布爾公式是真的全量詞化布爾公式 FARMULA-GAME 是 PSPACE 完全的公式公式 = x1 x2 x3 是是 TRUE 的條件是：的條件是

39、：存在存在 x1 的某種賦值，使得對于的某種賦值，使得對于 x2 的任意賦值，存在的任意賦值，存在 x3 的某種賦值，使的某種賦值，使得得等等，其中等等，其中 在這些變量的賦值下是在這些變量的賦值下是 TRUE。類似地，選手類似地，選手 E 在與在與 關(guān)聯(lián)的博奔中有必勝策略的條件是：關(guān)聯(lián)的博奔中有必勝策略的條件是：選手選手 E 可以給可以給 x1 賦某個值，使得對于賦某個值，使得對于 x2 的任意賦值，選手的任意賦值，選手 E 可以給可以給 x3 賦賦一個值，使得一個值，使得等等，等等， 在變量的這些賦值下為在變量的這些賦值下為 TRUE 。當(dāng)公式不在存在量詞與全稱量詞之間交替時，同樣的推理也

40、能成立。當(dāng)公式不在存在量詞與全稱量詞之間交替時，同樣的推理也能成立。如果如果 的形式為的形式為 x1 , x2 , x3 x4 , x5 x6 ，選手選手 A 在公式博弈中走頭三步，給在公式博弈中走頭三步，給 x1 , x2 和和 x3 賊值；然后選手賊值；然后選手 E 走兩次，走兩次，給給 x4 和和 x5 賊值；最后選手賊值；最后選手 A 給給x6 賦一個值。賦一個值。因此，因此， TQBE 恰好當(dāng)恰好當(dāng) FARMULA-GAME 時成立，由定理時成立，由定理8.8，本定理，本定理成立。成立。廣義地理學(xué)地理學(xué)地理學(xué)q 一種兒童一種兒童游戲。游戲。q 選手們選手們輪流輪流給世界各地的城市命名

41、。給世界各地的城市命名。q 每一座選中的城市的每一座選中的城市的首字母必須與前一座城市的尾字母相首字母必須與前一座城市的尾字母相同，不得重復(fù)同，不得重復(fù)。q 游戲游戲從某指定的起始城市開始從某指定的起始城市開始，以某方，以某方無法延續(xù)而認輸為無法延續(xù)而認輸為止止。q 例如：例如： 開始：開始：Peoria PeoriaAmherstTucsonNashua 結(jié)束：直到某方被難倒結(jié)束：直到某方被難倒地理學(xué)圖類似成類似成語接龍語接龍結(jié)點是世結(jié)點是世界各地的界各地的城市城市廣義地理學(xué)q 按照地理學(xué)規(guī)則按照地理學(xué)規(guī)則翻譯翻譯為圖表示法為圖表示法一名選手從一名選手從指定的起始節(jié)點開始指定的起始節(jié)點開始，

42、然后選手們，然后選手們交替交替地挑地挑選結(jié)點，形成圖中的一條選結(jié)點，形成圖中的一條簡單路徑簡單路徑。要求是簡單路徑要求是簡單路徑 (即每個節(jié)點只能用即每個節(jié)點只能用 1 次次) 對應(yīng)于要求城對應(yīng)于要求城市市不能重復(fù)不能重復(fù)。第第 1 個個不能擴展路徑的選手輸?shù)舯荣惒荒軘U展路徑的選手輸?shù)舯荣?。廣義地理學(xué)游戲樣例廣義地理學(xué)游戲樣例選手選手I必勝必勝1 13 36 64 45 52 27 78 89 9從結(jié)點從結(jié)點1開始，開始，選手選手I先做選擇先做選擇廣義地理學(xué)游戲樣例廣義地理學(xué)游戲樣例選手選手II必勝必勝1 13 36 64 45 52 27 78 89 9從結(jié)點從結(jié)點1開始，選開始，選手手I先

43、做選擇先做選擇現(xiàn)在方向變成節(jié)現(xiàn)在方向變成節(jié)點點3節(jié)點節(jié)點6廣義地理學(xué)q 判定在廣義地理學(xué)游戲中哪一方有必勝策賂的問題是判定在廣義地理學(xué)游戲中哪一方有必勝策賂的問題是PSPACE全的。全的。q GG = | 在圖在圖 G 上以結(jié)點上以結(jié)點 b 起始的廣義地理學(xué)游戲中，起始的廣義地理學(xué)游戲中，選手選手 I 有必勝策略有必勝策略 GG 是是 PSPACE 完全的。完全的。證明略證明略廣義地理學(xué)下面的的算法判定在廣義地理學(xué)實例中，選手下面的的算法判定在廣義地理學(xué)實例中，選手I是否有必勝策略。換是否有必勝策略。換 句話說，它判定句話說，它判定GG。現(xiàn)證明它在多項式空間內(nèi)運行：?，F(xiàn)證明它在多項式空間內(nèi)運行

44、： M=“對輸入對輸入，G是有向圖，是有向圖，b是是G的結(jié)點：的結(jié)點： 1）若）若b出度為出度為0，則拒絕，因為選手，則拒絕，因為選手I立即輸。立即輸。 2）刪去結(jié)點）刪去結(jié)點b以及與它關(guān)聯(lián)的所有箭頭，得到一個新圖以及與它關(guān)聯(lián)的所有箭頭，得到一個新圖G1。 3）對于）對于b原先指向的每個節(jié)點原先指向的每個節(jié)點b1， b2， ， bk，在，在上遞歸上遞歸地調(diào)用地調(diào)用 M。 4）若所有調(diào)用都接受，則選手）若所有調(diào)用都接受，則選手 在原先博弈中有必勝策略，所以拒絕。在原先博弈中有必勝策略，所以拒絕。 否則，選手否則，選手I 沒有必勝策賂，而選手沒有必勝策賂，而選手I有必勝策略，因此接受。有必勝策略，

45、因此接受?！?7主要內(nèi)容主要內(nèi)容8.1 薩維奇定理薩維奇定理8.2 PSPACE 類類8.3 PSPACE 完全性完全性8.3.1 TQBF 問題問題8.3.2 博弈的必勝策略博弈的必勝策略8.3.3 廣義地理學(xué)廣義地理學(xué)8.4 L 類類 NL 類類8.5 NL 完全性完全性8.6 NL 等于等于 coNLL 類和 NL 類q 線性空間復(fù)雜性界限：線性空間復(fù)雜性界限：f (n)=nq 亞線性空間復(fù)雜性界限：亞線性空間復(fù)雜性界限：f (n)n在時間復(fù)雜性中不考慮亞線性，因為亞線性連輸入都不在時間復(fù)雜性中不考慮亞線性，因為亞線性連輸入都不能讀完。能讀完。亞線性空間復(fù)雜性中能讀完全部輸入，但沒有足夠

46、的空亞線性空間復(fù)雜性中能讀完全部輸入，但沒有足夠的空間存儲全部輸入。解決辦法是修改計算模型間存儲全部輸入。解決辦法是修改計算模型包含只包含只讀帶的兩帶圖靈機。讀帶的兩帶圖靈機。q 兩帶圖靈機兩帶圖靈機一條只讀輸入帶：相當(dāng)于一條只讀輸入帶：相當(dāng)于CD_ROM一條讀寫工作帶：可修改。一條讀寫工作帶：可修改。只有工作帶上被掃描的單元才構(gòu)成這種圖靈機的空間復(fù)只有工作帶上被掃描的單元才構(gòu)成這種圖靈機的空間復(fù)雜性。雜性。L 類和 NL 類L 是確定型圖靈機在對數(shù)空間內(nèi)可判定的語言類。是確定型圖靈機在對數(shù)空間內(nèi)可判定的語言類。 L SPACE(log n)NL是非確定型圖靈機在對數(shù)空間內(nèi)可判定的語言類。是非

47、確定型圖靈機在對數(shù)空間內(nèi)可判定的語言類。 NL NSPACE(log n)L 類和 NL 類40例例8.13 語言語言 A=0k1k | k 0 是是 L 的成員。在的成員。在7.1節(jié)中描述了一節(jié)中描述了一個判定個判定 A 的圖靈機，它左右來回掃描輸人，刪掉匹配的的圖靈機，它左右來回掃描輸人，刪掉匹配的 0 和和 1。該算法用線性空間記錄哪些位置已經(jīng)被刪掉，但可以修改。該算法用線性空間記錄哪些位置已經(jīng)被刪掉，但可以修改為只使用對數(shù)空間。為只使用對數(shù)空間。判定判定 A 的對數(shù)空間的對數(shù)空間 TM 不能刪除輸入帶上已經(jīng)匹配的不能刪除輸入帶上已經(jīng)匹配的 0 和和 1，因為該帶是只讀的。因為該帶是只讀

48、的。機器在工作帶上用二進制分別數(shù)機器在工作帶上用二進制分別數(shù) 0 和和 1 的數(shù)目。唯一需要的空的數(shù)目。唯一需要的空間是用來記錄這兩個計數(shù)器的。在二進制形式，每個計數(shù)器只間是用來記錄這兩個計數(shù)器的。在二進制形式，每個計數(shù)器只消耗對數(shù)空間，因此算法在消耗對數(shù)空間，因此算法在 O(log n) 空間內(nèi)運行。所以空間內(nèi)運行。所以 A L。L 類和 NL 類41例例8.14 語言語言 PATH = | G 是包含從是包含從 s 到到 t 的有向路的有向路徑的有向圖徑的有向圖 。定理。定理7.12證明證明 PATH 屬于屬于P，但是給出的算法，但是給出的算法消耗線性空間?，F(xiàn)在能否找到只消耗對數(shù)空間的算法

49、？消耗線性空間?，F(xiàn)在能否找到只消耗對數(shù)空間的算法？判定判定 PATH 的非確定型對數(shù)空間圖靈機從節(jié)點的非確定型對數(shù)空間圖靈機從節(jié)點 s 開始運算，開始運算，非確定地猜測從非確定地猜測從 s 到到 t 的路徑的每一步的路徑的每一步。機器在工作帶上只記錄每一步當(dāng)前節(jié)點的位置機器在工作帶上只記錄每一步當(dāng)前節(jié)點的位置，而不是整條路，而不是整條路徑徑 (否則將超出對數(shù)空間的要求否則將超出對數(shù)空間的要求)。機器從當(dāng)前節(jié)點所指向的節(jié)點中非確定地選擇下一個節(jié)點。機器從當(dāng)前節(jié)點所指向的節(jié)點中非確定地選擇下一個節(jié)點。它反復(fù)執(zhí)行這一操作，直到到達結(jié)點它反復(fù)執(zhí)行這一操作，直到到達結(jié)點 t 而接受，或者執(zhí)行而接受，或者執(zhí)行 m 步步以后拒絕，其中以后拒絕，其中 m 是圖中的節(jié)點數(shù)。是圖中的節(jié)點數(shù)。所以所以 PATH 屬于屬于 NL。L 類和 NL 類若若 M 是一個有是一個有單獨的只讀輸入帶單獨的只讀輸入帶的圖靈機，的圖靈機，w 是輸入是輸入,則則 M 在在 w 上的格局上的格局包含狀態(tài)、工作帶和兩個讀寫頭位包含狀態(tài)、工作帶和兩個讀寫頭位置。輸入置。輸入 w 不作