計(jì)算理論導(dǎo)引空間復(fù)雜性

計(jì)算理論導(dǎo)引空間復(fù)雜性第一頁(yè)，共四十八頁(yè)，編輯于2023年，星期五2主要內(nèi)容8.1薩維奇定理8.2PSPACE類(lèi)8.3PSPACE完全性

8.3.1TQBF問(wèn)題

8.3.2博弈的必勝策略

8.3.3廣義地理學(xué)8.4L類(lèi)NL類(lèi)8.5NL完全性8.6NL等于coNL第二頁(yè)，共四十八頁(yè)，編輯于2023年，星期五空間復(fù)雜度定義8.1令M

是一個(gè)在所有輸入上都停機(jī)的確定型圖靈機(jī)。M的空間復(fù)雜度是一個(gè)函數(shù)f:NN，其中f(n)是M在任何長(zhǎng)為

n的輸入上掃描帶方格的最大數(shù)。若M的空間復(fù)雜度為f(n)，也稱(chēng)M在空間f(n)內(nèi)運(yùn)。如果M

是對(duì)所有輸入在所有分支上都停機(jī)的非確定型圖靈機(jī)，則定義它的空間復(fù)雜度f(wàn)(n)

為M在任何長(zhǎng)為n的輸入上，在任何計(jì)算分支上所掃描的帶方格的最大數(shù)。通常用漸進(jìn)記法估計(jì)圖靈機(jī)的空間復(fù)雜度。第三頁(yè)，共四十八頁(yè)，編輯于2023年，星期五空間復(fù)雜性類(lèi)定義8.2令f:NR+是一個(gè)函數(shù)，空間復(fù)雜性類(lèi)SPACE(f(n))和NSPACE(f(n))定義如下：SPACE(f(n))={L|L是被O(f(n))空間的確定型圖靈機(jī)判定的語(yǔ)言}NSPACE(f(n))={L|L是被O(f(n))空間的非確定型圖靈機(jī)判定的語(yǔ)言}

第四頁(yè)，共四十八頁(yè)，編輯于2023年，星期五例8.3例8.3證明用線性空間算法能求解SAT

問(wèn)題。M1=“對(duì)輸入<

>，

是布爾公式：1)對(duì)于中變量x1,…,xm

的每個(gè)真值賦值：2) 計(jì)算在該真值賦值下的值。3)若的值為1，則接受；否則拒絕?！憋@然機(jī)器M1

是在線性空間內(nèi)運(yùn)行，因?yàn)槊恳淮窝h(huán)都可以復(fù)用帶子上的同一部分。該機(jī)器只需存儲(chǔ)當(dāng)前的真值賦值，這只需消耗O(m)空間。因?yàn)樽兞繑?shù)m最多是輸入長(zhǎng)度n，所以該機(jī)器在空間O(n)內(nèi)運(yùn)行。第五頁(yè)，共四十八頁(yè)，編輯于2023年，星期五例：語(yǔ)言的非確定性空間復(fù)雜性例8.4令A(yù)LLNFA＝{<A>|A是一個(gè)NFA且L(A)=*}首先給出非確定型線性空間算法來(lái)判定該語(yǔ)言的補(bǔ)ALLNFA。算法的思想是利用非確定性猜測(cè)一個(gè)被NFA拒絕的字符串，然后用線性空間跟蹤該NFA，看它在特定時(shí)刻處在什么狀態(tài)。需要注意的是，此時(shí)還不知道該語(yǔ)言是否在NP或coNP中。N＝“對(duì)于輸入<M>，M

是NFA：1)置標(biāo)記于NFA的起始狀態(tài)。2)重復(fù)執(zhí)行下面的語(yǔ)句2q次，這里q

是M

的狀態(tài)數(shù)。3) 非確定地選擇一個(gè)輸入符號(hào)并移動(dòng)標(biāo)記到M

的相應(yīng)狀態(tài)，來(lái)模擬讀取那個(gè)符號(hào)。4)如果步驟2和3表明M

拒絕某些字符串，即如果在某一時(shí)刻所有標(biāo)記都不落在M

的接受狀態(tài)上，則接受；否則拒絕?！钡诹?yè)，共四十八頁(yè)，編輯于2023年，星期五例：語(yǔ)言的非確定性空間復(fù)雜性7如果M拒絕某個(gè)字符串，則它必定拒絕一個(gè)長(zhǎng)度不超過(guò)2q的字符串，因?yàn)樵谌魏伪痪芙^的更長(zhǎng)的字符串中，上面算法中所描述的標(biāo)記的位置分布必定重復(fù)出現(xiàn)。介于兩次重復(fù)出現(xiàn)之間的那一段字符串可以刪去，從而得到更短的被拒絕的字符串。所以N可判定ALLNFA

的補(bǔ)。該算法僅需要的空間是用來(lái)存放標(biāo)記的位置和重復(fù)計(jì)數(shù)器，這在線性空間就可以得到解決。因此，該算法在非確定的空間O(n)內(nèi)運(yùn)行。第七頁(yè)，共四十八頁(yè)，編輯于2023年，星期五薩維奇定理定理8.5對(duì)于任何函數(shù)f:NR+，其中f(n)n，NSPACE(f(n))

SPACE(f2(n))給定NTM的兩個(gè)格局c1

和c2，以及一個(gè)整數(shù)t，要求判定該NTM能否在t

步內(nèi)從c1變到c2，稱(chēng)該問(wèn)題為可產(chǎn)生性問(wèn)題。如果c1

是起始格局，c2是接受格局，t是非確定型機(jī)器所使用的最大步數(shù)，那么通過(guò)求解可產(chǎn)生問(wèn)題，就能夠判斷機(jī)器是否接受輸入。可以用一個(gè)確定的遞歸算法求解可產(chǎn)生問(wèn)題。運(yùn)算過(guò)程如下：尋找一個(gè)中間格局cm，遞歸地檢查c1

能否在t/2步內(nèi)到達(dá)cm，cm能否在t/2步內(nèi)到達(dá)c2，重復(fù)使用兩次遞歸檢查的空間可節(jié)省空間開(kāi)銷(xiāo)。遞歸的每一層需要O(f(n))空間來(lái)存儲(chǔ)一個(gè)格局。遞歸的深度是logt，t是非確定型機(jī)器在所有分支上可能消耗的最大時(shí)間，t=2O(f(n))，logt=O(f(n))。因此模擬過(guò)程需要O(f2(n))。第八頁(yè)，共四十八頁(yè)，編輯于2023年，星期五薩維奇定理的證明設(shè)N是在空間f(n)內(nèi)判定語(yǔ)言A的NTM。構(gòu)造一個(gè)判定A的確定型TMM。機(jī)器M利用過(guò)程CANYIELD，該過(guò)程檢查N的一個(gè)格局能否在指定的步數(shù)內(nèi)產(chǎn)生另一個(gè)格局。設(shè)w

是輸入到N的字符串。對(duì)于N在w上的格局c1、c2以及整數(shù)t，如果從格局c1

出發(fā)，N有一系列非確定的選擇能使它在t

步內(nèi)進(jìn)入格局c2

，則CANYIELD(c1,c2

,t)輸出接受，否則，CANYIELD輸出拒絕。CANYIELD=“對(duì)輸入

c1,c2

和t：1)若t=1，則直接檢查是否有c1=c2

，或者根據(jù)N的規(guī)則檢查c1能否在一步內(nèi)產(chǎn)生c2。如果其中之一成立，則接受；如果兩種情況都不成立，則拒絕。2)若t>1，則對(duì)于N在w上消耗空間f(n)的每一個(gè)格局cm：3) 運(yùn)行CANYIELD(c1,cm

,t/2)。4) 運(yùn)行CANYIELD(cm

,c2

,t/2)。5) 若第3和第4步都接受，則接受。6)若此時(shí)還沒(méi)有接受，則拒絕。”第九頁(yè)，共四十八頁(yè)，編輯于2023年，星期五薩維奇定理的證明現(xiàn)在定義M來(lái)模擬N。首先修改N，當(dāng)它接受時(shí)，把帶子清空并把讀寫(xiě)頭移到最左邊的單元，從而進(jìn)入稱(chēng)為caccept的格局。令cstart是N在w上的起始格局。選一個(gè)常數(shù)d，使得N在f(n)空間上的格局?jǐn)?shù)不超過(guò)2df(n)，其中n是w的長(zhǎng)度。

2df(n)是N在所有分支上的運(yùn)行時(shí)間的上界。M＝“對(duì)輸入w：

1)輸出CANYIELD(cstart，caccept，2df(n)

)的結(jié)果?！彼惴–ANYIELD顯然求解了可產(chǎn)生性問(wèn)題，因此M正確地模擬N。下面需要分析M，確信它在O(f(n))空間內(nèi)運(yùn)行。CANYIELD在遞歸調(diào)用自己時(shí)，它都把所處的步驟號(hào)、c1、c2和t

的都存儲(chǔ)在棧中，所以遞歸調(diào)用時(shí)返回時(shí)能恢復(fù)這些值。因此在遞歸的每一層需要增加O(f(n))空間。此外，遞歸的每一層把t的值減小一半。開(kāi)始時(shí)t

等于2df(n)，所以遞歸的深度是O(log2df(n))或O(f(n))，因此共消耗空間是O(f2(n))。第十頁(yè)，共四十八頁(yè)，編輯于2023年，星期五11主要內(nèi)容8.1薩維奇定理8.2PSPACE類(lèi)8.3PSPACE完全性

8.3.1TQBF問(wèn)題

8.3.2博弈的必勝策略

8.3.3廣義地理學(xué)8.4L類(lèi)NL類(lèi)8.5NL完全性8.6NL等于coNL第十一頁(yè)，共四十八頁(yè)，編輯于2023年，星期五PSPACE類(lèi)定義8.6PSPACE是在確定型圖靈機(jī)上、在多項(xiàng)式空間內(nèi)可判定的語(yǔ)言類(lèi)。換言之，PSPACE＝∪k

SPACE(nk)

PSPACE類(lèi)的非確定型版本NPSPACE，可以類(lèi)似地用NSPACE類(lèi)來(lái)定義。然而，任何多項(xiàng)式的平方仍是多項(xiàng)式，根據(jù)薩維奇定理，則NPSPACE=PSPACE

。在例8.3和8.4中，已經(jīng)說(shuō)明了SAT屬于SPACE(n)，

ALLNFA屬于coNSPACE(n)

，而根據(jù)薩維奇定理，確定型空間復(fù)雜度對(duì)補(bǔ)運(yùn)算封閉，所以ALLNFA也屬于SPACE(n2)。因此SAT和ALLNFA這兩個(gè)語(yǔ)言都在PSPACE中。第十二頁(yè)，共四十八頁(yè)，編輯于2023年，星期五PSPACE類(lèi)考察PSPACE與P和NP的關(guān)系。顯而易見(jiàn)，PPSPACE，因?yàn)檫\(yùn)行快的機(jī)器不可能消耗大量的空間。更精確地說(shuō)，當(dāng)t(n)≥n時(shí)，由于在每個(gè)計(jì)算步上最多能訪問(wèn)一個(gè)新單元，因此，任何在時(shí)間t(n)內(nèi)運(yùn)行的機(jī)器最多能消耗t(n)的空間。類(lèi)似地，NPNPSPACE

，所以NPPSPACE

。反過(guò)來(lái)，根據(jù)圖靈機(jī)的空間復(fù)雜性可以界定它的時(shí)間復(fù)雜性。對(duì)于f(n)≥n

，通過(guò)簡(jiǎn)單推廣引理5.7的證明可知，一個(gè)消耗f(n)空間的TM至多有f(n)2O(f(n))個(gè)不同的格局，也必定在時(shí)間f(n)2O(f(n))內(nèi)運(yùn)行，得出：

PSPACEEXPTIME=∪kTIME(2nk)

PNPPSPACE=NPSPACEEXPTIME第十三頁(yè)，共四十八頁(yè)，編輯于2023年，星期五14主要內(nèi)容8.1薩維奇定理8.2PSPACE類(lèi)8.3PSPACE完全性

8.3.1TQBF問(wèn)題

8.3.2博弈的必勝策略

8.3.3廣義地理學(xué)8.4L類(lèi)NL類(lèi)8.5NL完全性8.6NL等于coNL第十四頁(yè)，共四十八頁(yè)，編輯于2023年，星期五PSPACE完全性定義8.7語(yǔ)言B

是PSPACE完全的。若它滿(mǎn)足下面兩個(gè)條件：1)B

屬于PSPACE。2)PSPACE中的每一個(gè)語(yǔ)言A多項(xiàng)式時(shí)間可歸約到B。若B

只滿(mǎn)足條件2，則稱(chēng)它為PSPACE難的。第十五頁(yè)，共四十八頁(yè)，編輯于2023年，星期五TQBF

問(wèn)題量詞：、 對(duì)于自然數(shù)，語(yǔ)句x[x+1>x]為真。y[y+y=y]為假。轄域：量詞的作用范圍。前束范式：形如

=Q1x1

Q2

x2…QkxkB，Qi為或量詞化布爾公式：帶量詞的布爾公式（必須是前束范式）。全量詞化：公式中的每個(gè)變量都出現(xiàn)在某一量詞的轄域中。TQBF

問(wèn)題就是要判定一個(gè)全量詞化的布爾公式是真是假。TQBF={<>|是真的全量詞化的布爾公式}第十六頁(yè)，共四十八頁(yè)，編輯于2023年，星期五TQBF

問(wèn)題定理8.8TQBF

是PSPACE完全的。證明思路(1)為了證明TQBF屬于PSPACE，給出一個(gè)簡(jiǎn)單的算法。該算法首先給變量賦值，然后遞歸地計(jì)算公式在這些值下的真值。從這些信息中算法就能確定原量化公式的真值。(2)為了證明PSPACE中的每個(gè)語(yǔ)言A在多項(xiàng)式時(shí)間內(nèi)可歸約到TQBF，從判定A的多項(xiàng)式空間界限圖靈機(jī)開(kāi)始。然后給出多項(xiàng)式時(shí)間歸約，它把一個(gè)字符串映射為一個(gè)量詞化的布爾公式ф，ф模擬機(jī)器對(duì)這個(gè)輸入的計(jì)算。公式為真的充分必要條件是機(jī)器接受。 改用一種與薩維奇定理的證明相關(guān)的技術(shù)來(lái)構(gòu)造公式。該公式把畫(huà)面分成兩半，利用全稱(chēng)量詞的功能，用公式的同一部分來(lái)代表每一半。結(jié)果產(chǎn)生短得多的公式。第十七頁(yè)，共四十八頁(yè)，編輯于2023年，星期五TQBF

問(wèn)題首先，給出一個(gè)判定TQBF

的多項(xiàng)式空間算法：T

＝“對(duì)輸入<>，是一個(gè)全量詞化的布爾公式：1)若不含量詞，則它是一個(gè)只有常數(shù)的表達(dá)式。計(jì)算的值，若為真，則接受；否則，拒絕。2)若等于x

，在上遞歸地調(diào)用T，首先用0替換x，然后用1替換x。只要有一個(gè)結(jié)果是接受，則接受；否則，拒絕。3)若等于x

，在上遞歸地調(diào)用T，首先用0替換x，然后用1替換x。若兩個(gè)結(jié)果都能接受，則接受；否則，拒絕。”算法T

顯然判定TQBF

?？臻g復(fù)雜性：它遞歸的深度最多等于變量的個(gè)數(shù)。在每一層只需存儲(chǔ)一個(gè)變量的值，所以全部空間消耗是O(m)，其中m是中出現(xiàn)的變量的個(gè)數(shù)。因此T

在線性空間內(nèi)運(yùn)行。第十八頁(yè)，共四十八頁(yè)，編輯于2023年，星期五TQBF

問(wèn)題下面，證明TQBF是PSPACE難的。設(shè)A是一個(gè)由TMM

在nk空間內(nèi)判定的語(yǔ)言，k是某個(gè)常數(shù)。下面給出一個(gè)從A到TQBF的多項(xiàng)式時(shí)間歸約。該歸約把字符串w映射為一個(gè)量詞化的布爾公式

，為真當(dāng)且僅當(dāng)M

接受

w。為了說(shuō)明怎樣構(gòu)造，需解決一個(gè)更一般的問(wèn)題。利用兩個(gè)代表格局的變量集合c1和c2及一個(gè)數(shù)t>0，構(gòu)造一個(gè)公式c1,c2,t。如果把c1和c2賦為實(shí)際的格局，則該公式為真當(dāng)且僅當(dāng)M

能夠在最多t步內(nèi)從c1到達(dá)c2。然后，可以令是公式cstart,caccept,h，其中h=2df(n)

，d是一個(gè)選取的常數(shù)，使得M

在長(zhǎng)為n的輸入上可能的格局?jǐn)?shù)不超過(guò)2df(n)

。這里，令f(n)=nk。為了方便，假設(shè)t

是2的冪。類(lèi)似庫(kù)克-列文定理的證明，該公式對(duì)帶單元的內(nèi)容編碼。對(duì)應(yīng)于單元的可能設(shè)置，每個(gè)單元有幾個(gè)相關(guān)的變量，每個(gè)帶符號(hào)和狀態(tài)有一個(gè)變量。每個(gè)格局有nk個(gè)單元，所以用O(nk)個(gè)變量編碼。第十九頁(yè)，共四十八頁(yè)，編輯于2023年，星期五TQBF問(wèn)題若t=1，則容易構(gòu)造c1,c2,t。設(shè)計(jì)公式，使之表達(dá)要么c1

等于c2，要么c1能在M

的一步內(nèi)變到c2

。為了表達(dá)相等性，使用一個(gè)布爾表達(dá)式來(lái)表示：代表c1

的每一個(gè)變量與代表c2

的相應(yīng)變量包含同樣的布爾值。為表達(dá)第二種可能性，采用庫(kù)克-列文定理的證明中給出的技巧，構(gòu)造布爾表達(dá)式表示，代表c1的每個(gè)三元組的值能正確產(chǎn)生相應(yīng)的c2

的三元組的值，從而就能夠表達(dá)c1

在M

的一步內(nèi)產(chǎn)生c2。若t>1，遞歸的構(gòu)造c1,c2,t。作為預(yù)演，先嘗試一種不太好的想法，然后再修正它。令：c1,c2,t

=m1[c1,m1,t/2m1,c2,t/2]符號(hào)m1表示M的一個(gè)格局。m1是x1,...,xf的縮寫(xiě)，其中l(wèi)=O(nk)，

x1,...,xf

是對(duì)m1

編碼的變量。所以c1,c2,t

的這個(gè)構(gòu)造的含義是：如果存在某個(gè)中間格局m1

，使得M

在至多t/2步內(nèi)從c1

變到m1，并且在至多t/2步內(nèi)從m1

變到c2，那么M

就能在至多t

步內(nèi)從c1

變到c2。然后再遞歸地構(gòu)造c1,m1,t/2和m1,c2,t/2

這兩個(gè)公式。第二十頁(yè)，共四十八頁(yè)，編輯于2023年，星期五TQBF問(wèn)題公式c1,c2,t

具有正確值。換言之，只要M

能在t

步內(nèi)從c1變到c2，它就是TRUE。然而，它太長(zhǎng)了。構(gòu)造過(guò)程中涉及的遞歸的每一層都把t

的值減小一半，卻把公式的長(zhǎng)度增加了大約一倍，最后導(dǎo)致公式的長(zhǎng)度大約是t，開(kāi)始時(shí)t=2df(n)，所以這種方法結(jié)出的公式是指數(shù)長(zhǎng)的。為了縮短公式的長(zhǎng)度，除了使用量詞以外，再利用量詞。令

c1,c2,t

=m1(c3,c4){(c1,m1),(m1,c2)}[c3,c4,t/2

]新引入的變量代表格局c3

和c4，它允許把兩個(gè)遞歸的子公式“折疊”為一個(gè)子公式，而保持原來(lái)的意思。通過(guò)寫(xiě)成

(c3,c4){(c1,m1),(m1,c2)}就指明了代表格局c3

和c4

的變量可以分別取c1和m1的變量的值，或者m1和c2

的變量的值，結(jié)果公式c3,c4,t/2

在兩種情況下都為真?？梢园呀Y(jié)構(gòu)(c3,c4){(c1,m1),(m1,c2)}替換為等價(jià)的結(jié)構(gòu)x[(x=yx=z)…]

，從而得到語(yǔ)法正確的量化布爾公式。為了計(jì)算公式個(gè)cstart，caccept,h的長(zhǎng)度，其中h=2df(n)

，注意到遞歸增加的那部分公式的長(zhǎng)度與格局的長(zhǎng)度呈線性關(guān)系，所以長(zhǎng)度是O(f(n))。遞歸的層數(shù)是log2df(n)或O(f(n))。所以所得到的公式的長(zhǎng)度是O(f2(n))。第二十一頁(yè)，共四十八頁(yè)，編輯于2023年，星期五博弈的必勝策略博奕論：每個(gè)游戲常有2個(gè)以上的參加者，他們(局中人)在游戲中都有自己的切身利益，每個(gè)局中人都有自己的可行行動(dòng)集供自己選擇，這種選擇毫無(wú)疑問(wèn)地會(huì)影響到其他局中人的切身利益。游戲中各個(gè)局中人理性地采取/選擇自己的策略行為，使得在這種相互制約相互影響的依存關(guān)系中，盡可能提高自己的利益所得，這正是游戲理論的關(guān)鍵所得。要點(diǎn)：博奕的各方都是理性的各人的選擇都是為取得利益的最大化

第二十二頁(yè)，共四十八頁(yè)，編輯于2023年，星期五囚徒困境1950年，就職于蘭德公司的梅里爾·弗勒德（MerrillFlood）和梅爾文·德雷希爾（MelvinDresher）擬定出相關(guān)困境的理論，后來(lái)由顧問(wèn)艾伯特·塔克（AlbertTucker）以囚徒方式闡述，并命名為“囚徒困境”。經(jīng)典的囚徒困境如下： 兩個(gè)嫌犯被捕后被關(guān)在相互隔離的牢房中。他們面臨的選擇是：或者坦白或者保持沉默（即不坦白）。他們被告知：①如果某個(gè)嫌疑犯坦白而其同伙不坦白，則坦白者可獲自由而拒不坦白者要被判10年監(jiān)禁；②如果二人都坦白，則二人都被判5年監(jiān)禁；③如果二人都不坦白，則二人皆被判1年監(jiān)禁。上述情況我們亦可用一支付矩陣表示如下：

嫌疑犯乙

坦白沉默

嫌疑犯甲坦白-5,-5

0,-10

沉默-10,0

-1,-1

在這種情況下，兩個(gè)嫌犯將如何決策和選擇呢？第二十三頁(yè)，共四十八頁(yè)，編輯于2023年，星期五博弈的必勝策略博奕和量詞緊密相關(guān)一個(gè)量化語(yǔ)句一個(gè)博弈 作用：描述和解釋該語(yǔ)句的含義一個(gè)博弈一個(gè)量化語(yǔ)句 作用：理解該博弈的復(fù)雜性例：前束范式的量詞化布爾公式

f=$x1"x2$x3…Qxk[]Q:$/"，--去掉量詞的公式

f與下面的博弈關(guān)聯(lián)：

2名選手A,E，輪流為x1,x2,x3,…,xk選值第二十四頁(yè)，共四十八頁(yè)，編輯于2023年，星期五博弈的必勝策略選手E所對(duì)應(yīng)的量詞選手A所對(duì)應(yīng)的量詞選手E取值選手A取值對(duì)變量進(jìn)行處理的語(yǔ)句TRUE:E勝FALSE:A勝其中A對(duì)任意量詞約束的變量選值；E對(duì)存在量詞約束的變量選值第二十五頁(yè)，共四十八頁(yè)，編輯于2023年，星期五例8.9 f1=$x1"x2$x3[(x1úx2)ù(x2úx3)ù(x2úx3)]E確定的變量值A(chǔ)確定的變量值設(shè)E：x1=1;A：x2=0;E：x3=1;=1,E贏取值相反E必勝：設(shè)E：x1=1/0;A：x2=0;E：x3=1/0;=0,A贏A必勝：f2=$x1"x2$x3[(x1úx2)ù(x2úx3)ù(x2úx3)]必勝策略一個(gè)選手有必勝策略，如果他在博弈雙方都下出最佳步驟時(shí)能贏第二十六頁(yè)，共四十八頁(yè)，編輯于2023年，星期五博弈的必勝策略判定在與某具體公式關(guān)聯(lián)的公式博弈中哪方有必勝策略的問(wèn)題是PSPACE完全的。FORMULA-GAME={<>|在與關(guān)聯(lián)的公式博奕中選手E有必勝策略}第二十七頁(yè)，共四十八頁(yè)，編輯于2023年，星期五博弈的必勝策略定理8.10FARMULA-GAME是PSPACE完全的。要證FORMULA-GAME是PSPACE完全的FORMULA-GAME=TQBFFORMULA-GAME={<>|是真的全量詞化布爾公式}第二十八頁(yè)，共四十八頁(yè)，編輯于2023年，星期五FARMULA-GAME

是PSPACE完全的公式=x1x2x3…[]是TRUE的條件是： 存在x1的某種賦值，使得對(duì)于x2

的任意賦值，存在x3的某種賦值，使得…等等，其中在這些變量的賦值下是TRUE。類(lèi)似地，選手E在與關(guān)聯(lián)的博奔中有必勝策略的條件是： 選手E可以給x1賦某個(gè)值，使得對(duì)于x2的任意賦值，選手E可以給x3賦一個(gè)值，使得…等等，在變量的這些賦值下為T(mén)RUE。當(dāng)公式不在存在量詞與全稱(chēng)量詞之間交替時(shí)，同樣的推理也能成立。 如果的形式為

x1,x2

,x3

x4

,x5x6[]， 選手A在公式博弈中走頭三步，給x1,x2和x3賊值；然后選手E走兩次，給x4和x5賊值；最后選手A給x6賦一個(gè)值。因此，TQBE

恰好當(dāng)FARMULA-GAME時(shí)成立，由定理8.8，本定理成立。第二十九頁(yè)，共四十八頁(yè)，編輯于2023年，星期五廣義地理學(xué)地理學(xué)一種兒童游戲。選手們輪流給世界各地的城市命名。每一座選中的城市的首字母必須與前一座城市的尾字母相同，不得重復(fù)。游戲從某指定的起始城市開(kāi)始，以某方無(wú)法延續(xù)而認(rèn)輸為止。例如：

開(kāi)始：PeoriaPeoriaAmherstTucsonNashua…

結(jié)束：直到某方被難倒第三十頁(yè)，共四十八頁(yè)，編輯于2023年，星期五地理學(xué)圖類(lèi)似成語(yǔ)接龍結(jié)點(diǎn)是世界各地的城市第三十一頁(yè)，共四十八頁(yè)，編輯于2023年，星期五廣義地理學(xué)按照地理學(xué)規(guī)則翻譯為圖表示法一名選手從指定的起始節(jié)點(diǎn)開(kāi)始，然后選手們交替地挑選結(jié)點(diǎn)，形成圖中的一條簡(jiǎn)單路徑。要求是簡(jiǎn)單路徑(即每個(gè)節(jié)點(diǎn)只能用1次)對(duì)應(yīng)于要求城市不能重復(fù)。第1個(gè)不能擴(kuò)展路徑的選手輸?shù)舯荣?。第三十二?yè)，共四十八頁(yè)，編輯于2023年，星期五廣義地理學(xué)游戲樣例選手I必勝136452789從結(jié)點(diǎn)1開(kāi)始，選手I先做選擇第三十三頁(yè)，共四十八頁(yè)，編輯于2023年，星期五廣義地理學(xué)游戲樣例選手II必勝136452789從結(jié)點(diǎn)1開(kāi)始，選手I先做選擇現(xiàn)在方向變成節(jié)點(diǎn)3節(jié)點(diǎn)6第三十四頁(yè)，共四十八頁(yè)，編輯于2023年，星期五廣義地理學(xué)判定在廣義地理學(xué)游戲中哪一方有必勝策賂的問(wèn)題是PSPACE全的。GG={<G,b>|在圖G上以結(jié)點(diǎn)b

起始的廣義地理學(xué)游戲中，選手I有必勝策略}定理8.11GG

是PSPACE完全的。證明略第三十五頁(yè)，共四十八頁(yè)，編輯于2023年，星期五廣義地理學(xué)下面的的算法判定在廣義地理學(xué)實(shí)例中，選手I是否有必勝策略。換句話(huà)說(shuō)，它判定GG。現(xiàn)證明它在多項(xiàng)式空間內(nèi)運(yùn)行：

M=“對(duì)輸入<G，b>，G是有向圖，b是G的結(jié)點(diǎn)：

1）若b出度為0，則拒絕，因?yàn)檫x手I立即輸。

2）刪去結(jié)點(diǎn)b以及與它關(guān)聯(lián)的所有箭頭，得到一個(gè)新圖G1。

3）對(duì)于b原先指向的每個(gè)節(jié)點(diǎn)b1，b2，…，bk，在<G1，bi>上遞歸地調(diào)用M。

4）若所有調(diào)用都接受，則選手在原先博弈中有必勝策略，所以拒絕。

否則，選手I沒(méi)有必勝策賂，而選手I有必勝策略，因此接受?！钡谌?yè)，共四十八頁(yè)，編輯于2023年，星期五37主要內(nèi)容8.1薩維奇定理8.2PSPACE類(lèi)8.3PSPACE完全性

8.3.1TQBF問(wèn)題

8.3.2博弈的必勝策略

8.3.3廣義地理學(xué)8.4L類(lèi)NL類(lèi)8.5NL完全性8.6NL等于coNL第三十七頁(yè)，共四十八頁(yè)，編輯于2023年，星期五L類(lèi)和NL類(lèi)線性空間復(fù)雜性界限：f(n)=n亞線性空間復(fù)雜性界限：f(n)<n在時(shí)間復(fù)雜性中不考慮亞線性，因?yàn)閬喚€性連輸入都不能讀完。亞線性空間復(fù)雜性中能讀完全部輸入，但沒(méi)有足夠的空間存儲(chǔ)全部輸入。解決辦法是修改計(jì)算模型——包含只讀帶的兩帶圖靈機(jī)。兩帶圖靈機(jī)一條只讀輸入帶：相當(dāng)于CD_ROM一條讀寫(xiě)工作帶：可修改。只有工作帶上被掃描的單元才構(gòu)成這種圖靈機(jī)的空間復(fù)雜性。第三十八頁(yè)，共四十八頁(yè)，編輯于2023年，星期五L類(lèi)和NL類(lèi)定義8.12L是確定型圖靈機(jī)在對(duì)數(shù)空間內(nèi)可判定的語(yǔ)言類(lèi)。

L＝SPACE(logn)NL是非確定型圖靈機(jī)在對(duì)數(shù)空間內(nèi)可判定的語(yǔ)言類(lèi)。

NL＝NSPACE(logn)第三十九頁(yè)，共四十八頁(yè)，編輯于2023年，星期五L類(lèi)和NL類(lèi)40例8.13語(yǔ)言A={0k1k|k0}是L的成員。在7.1節(jié)中描述了一個(gè)判定A

的圖靈機(jī)，它左右來(lái)回掃描輸人，刪掉匹配的0和1。該算法用線性空間記錄哪些位置已經(jīng)被刪掉，但可以修改為只使用對(duì)數(shù)空間。判定A

的對(duì)數(shù)空間TM不能刪除輸入帶上已經(jīng)匹配的0和1，因?yàn)樵搸侵蛔x的。機(jī)器在工作帶上用二進(jìn)制分別數(shù)0和1的數(shù)目。唯一需要的空間是用來(lái)記錄這兩個(gè)計(jì)數(shù)器的。在二進(jìn)制形式，每個(gè)計(jì)數(shù)器只消耗對(duì)數(shù)空間，因此算法在O(logn)空間內(nèi)運(yùn)行。所以AL。第四十頁(yè)，共四十八頁(yè)，編輯于2023年，星期五L類(lèi)和NL類(lèi)41例8.14語(yǔ)言PATH={<G,s,t>

|G是包含從s

到t

的有向路徑的有向圖}。定理7.12證明PATH

屬于P，但是給出的算法消耗線性空間。現(xiàn)在能否找到只消耗對(duì)數(shù)空間的算法？判定PATH

的非確定型對(duì)數(shù)空間圖靈機(jī)從節(jié)點(diǎn)s

開(kāi)始運(yùn)算，非確定地猜測(cè)從s

到t

的路徑的每一步。機(jī)器在工作帶上只記錄每一步當(dāng)前節(jié)點(diǎn)的位置，而不是整條路徑(否則將超出對(duì)數(shù)空間的要求)。機(jī)器從當(dāng)前節(jié)點(diǎn)所指向的節(jié)點(diǎn)中非確定地選擇下一個(gè)節(jié)點(diǎn)。它反復(fù)執(zhí)行這一操作，直到到達(dá)結(jié)點(diǎn)t

而接受，或者執(zhí)行m

步以后拒絕，其中m

是圖中的節(jié)點(diǎn)數(shù)。所以PATH

屬于NL。第四十一頁(yè)，共四十八頁(yè)，編輯于2023年，星期五L類(lèi)和NL類(lèi)定義8.15若M是一個(gè)有單獨(dú)的只讀輸入帶的圖靈機(jī)，w是輸入,則M在w上的格局包含狀態(tài)、工作帶和兩個(gè)讀寫(xiě)頭位置。輸入w不作為M在w上的格局的一部分。如果M

在f(n)空間內(nèi)運(yùn)行，w是長(zhǎng)為n

的輸入，則M

在w

上的格局?jǐn)?shù)是n2O