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

計算理論導(dǎo)引空間復(fù)雜性第一頁，共四十八頁，2022年，8月28日2主要內(nèi)容8.1薩維奇定理8.2PSPACE類8.3PSPACE完全性

8.3.1TQBF問題

8.3.2博弈的必勝策略

8.3.3廣義地理學(xué)8.4L類NL類8.5NL完全性8.6NL等于coNL第二頁，共四十八頁，2022年，8月28日空間復(fù)雜度定義8.1令M

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

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

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

為M在任何長為n的輸入上，在任何計算分支上所掃描的帶方格的最大數(shù)。通常用漸進記法估計圖靈機的空間復(fù)雜度。第三頁，共四十八頁，2022年，8月28日空間復(fù)雜性類定義8.2令f:NR+是一個函數(shù)，空間復(fù)雜性類SPACE(f(n))和NSPACE(f(n))定義如下：SPACE(f(n))={L|L是被O(f(n))空間的確定型圖靈機判定的語言}NSPACE(f(n))={L|L是被O(f(n))空間的非確定型圖靈機判定的語言}

第四頁，共四十八頁，2022年，8月28日例8.3例8.3證明用線性空間算法能求解SAT

問題。M1=“對輸入<

>，

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

的每個真值賦值：2) 計算在該真值賦值下的值。3)若的值為1，則接受；否則拒絕。”顯然機器M1

是在線性空間內(nèi)運行，因為每一次循環(huán)都可以復(fù)用帶子上的同一部分。該機器只需存儲當(dāng)前的真值賦值，這只需消耗O(m)空間。因為變量數(shù)m最多是輸入長度n，所以該機器在空間O(n)內(nèi)運行。第五頁，共四十八頁，2022年，8月28日例：語言的非確定性空間復(fù)雜性例8.4令A(yù)LLNFA＝{<A>|A是一個NFA且L(A)=*}首先給出非確定型線性空間算法來判定該語言的補ALLNFA。算法的思想是利用非確定性猜測一個被NFA拒絕的字符串，然后用線性空間跟蹤該NFA，看它在特定時刻處在什么狀態(tài)。需要注意的是，此時還不知道該語言是否在NP或coNP中。N＝“對于輸入<M>，M

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

是M

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

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

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

的接受狀態(tài)上，則接受；否則拒絕?！钡诹摚菜氖隧?，2022年，8月28日例：語言的非確定性空間復(fù)雜性7如果M拒絕某個字符串，則它必定拒絕一個長度不超過2q的字符串，因為在任何被拒絕的更長的字符串中，上面算法中所描述的標(biāo)記的位置分布必定重復(fù)出現(xiàn)。介于兩次重復(fù)出現(xiàn)之間的那一段字符串可以刪去，從而得到更短的被拒絕的字符串。所以N可判定ALLNFA

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

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

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

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

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

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

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

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

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

，則CANYIELD(c1,c2

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

c1,c2

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

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

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

,c2

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

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

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

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

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

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

8.3.1TQBF問題

8.3.2博弈的必勝策略

8.3.3廣義地理學(xué)8.4L類NL類8.5NL完全性8.6NL等于coNL第十一頁，共四十八頁，2022年，8月28日PSPACE類定義8.6PSPACE是在確定型圖靈機上、在多項式空間內(nèi)可判定的語言類。換言之，PSPACE＝∪k

SPACE(nk)

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

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

ALLNFA屬于coNSPACE(n)

，而根據(jù)薩維奇定理，確定型空間復(fù)雜度對補運算封閉，所以ALLNFA也屬于SPACE(n2)。因此SAT和ALLNFA這兩個語言都在PSPACE中。第十二頁，共四十八頁，2022年，8月28日PSPACE類考察PSPACE與P和NP的關(guān)系。顯而易見，PPSPACE，因為運行快的機器不可能消耗大量的空間。更精確地說，當(dāng)t(n)≥n時，由于在每個計算步上最多能訪問一個新單元，因此，任何在時間t(n)內(nèi)運行的機器最多能消耗t(n)的空間。類似地，NPNPSPACE

，所以NPPSPACE

。反過來，根據(jù)圖靈機的空間復(fù)雜性可以界定它的時間復(fù)雜性。對于f(n)≥n

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

PSPACEEXPTIME=∪kTIME(2nk)

PNPPSPACE=NPSPACEEXPTIME第十三頁，共四十八頁，2022年，8月28日14主要內(nèi)容8.1薩維奇定理8.2PSPACE類8.3PSPACE完全性

8.3.1TQBF問題

8.3.2博弈的必勝策略

8.3.3廣義地理學(xué)8.4L類NL類8.5NL完全性8.6NL等于coNL第十四頁，共四十八頁，2022年，8月28日PSPACE完全性定義8.7語言B

是PSPACE完全的。若它滿足下面兩個條件：1)B

屬于PSPACE。2)PSPACE中的每一個語言A多項式時間可歸約到B。若B

只滿足條件2，則稱它為PSPACE難的。第十五頁，共四十八頁，2022年，8月28日TQBF

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

=Q1x1

Q2

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

問題就是要判定一個全量詞化的布爾公式是真是假。TQBF={<>|是真的全量詞化的布爾公式}第十六頁，共四十八頁，2022年，8月28日TQBF

問題定理8.8TQBF

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

問題首先，給出一個判定TQBF

的多項式空間算法：T

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

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

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

顯然判定TQBF

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

在線性空間內(nèi)運行。第十八頁，共四十八頁，2022年，8月28日TQBF

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

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

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

接受

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

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

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

在長為n的輸入上可能的格局數(shù)不超過2df(n)

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

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

等于c2，要么c1能在M

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

。為了表達相等性，使用一個布爾表達式來表示：代表c1

的每一個變量與代表c2

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

的三元組的值，從而就能夠表達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]符號m1表示M的一個格局。m1是x1,...,xf的縮寫，其中l(wèi)=O(nk)，

x1,...,xf

是對m1

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

的這個構(gòu)造的含義是：如果存在某個中間格局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

這兩個公式。第二十頁，共四十八頁，2022年，8月28日TQBF問題公式c1,c2,t

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

能在t

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

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

c1,c2,t

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

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

和c4，它允許把兩個遞歸的子公式“折疊”為一個子公式，而保持原來的意思。通過寫成

(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é)構(gòu)x[(x=yx=z)…]

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

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

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

嫌疑犯乙

坦白沉默

嫌疑犯甲坦白-5,-5

0,-10

沉默-10,0

-1,-1

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

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

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

2名選手A,E，輪流為x1,x2,x3,…,xk選值第二十四頁，共四十八頁，2022年，8月28日博弈的必勝策略選手E所對應(yīng)的量詞選手A所對應(yīng)的量詞選手E取值選手A取值對變量進行處理的語句TRUE:E勝FALSE:A勝其中A對任意量詞約束的變量選值；E對存在量詞約束的變量選值第二十五頁，共四十八頁，2022年，8月28日例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)]必勝策略一個選手有必勝策略，如果他在博弈雙方都下出最佳步驟時能贏第二十六頁，共四十八頁，2022年，8月28日博弈的必勝策略判定在與某具體公式關(guān)聯(lián)的公式博弈中哪方有必勝策略的問題是PSPACE完全的。FORMULA-GAME={<>|在與關(guān)聯(lián)的公式博奕中選手E有必勝策略}第二十七頁，共四十八頁，2022年，8月28日博弈的必勝策略定理8.10FARMULA-GAME是PSPACE完全的。要證FORMULA-GAME是PSPACE完全的FORMULA-GAME=TQBFFORMULA-GAME={<>|是真的全量詞化布爾公式}第二十八頁，共四十八頁，2022年，8月28日FARMULA-GAME

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

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

x1,x2

,x3

x4

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

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

開始：PeoriaPeoriaAmherstTucsonNashua…

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

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

是PSPACE完全的。證明略第三十五頁，共四十八頁，2022年，8月28日廣義地理學(xué)下面的的算法判定在廣義地理學(xué)實例中，選手I是否有必勝策略。換句話說，它判定GG?，F(xiàn)證明它在多項式空間內(nèi)運行：

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

1）若b出度為0，則拒絕，因為選手I立即輸。

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

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

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

否則，選手I沒有必勝策賂，而選手I有必勝策略，因此接受?！钡谌?，共四十八頁，2022年，8月28日37主要內(nèi)容8.1薩維奇定理8.2PSPACE類8.3PSPACE完全性

8.3.1TQBF問題

8.3.2博弈的必勝策略

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

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

NL＝NSPACE(logn)第三十九頁，共四十八頁，2022年，8月28日L類和NL類40例8.13語言A={0k1k|k0}是L的成員。在7.1節(jié)中描述了一個判定A

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

的對數(shù)空間TM不能刪除輸入帶上已經(jīng)匹配的0和1，因為該帶是只讀的。機器在工作帶上用二進制分別數(shù)0和1的數(shù)目。唯一需要的空間是用來記錄這兩個計數(shù)器的。在二進制形式，每個計數(shù)器只消耗對數(shù)空間，因此算法在O(logn)空間內(nèi)運行。所以AL。第四十頁，共四十八頁，2022年，8月28日L類和NL類41例8.14語言PATH={<G,s,t>

|G是包含從s

到t

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

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

的非確定型對數(shù)空間圖靈機從節(jié)點s

開始運算，非確定地猜測從s

到t

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

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

步以后拒絕，其中m

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

屬于NL。第四十一頁，共四十八頁，2022年，8月28日L類和NL類定義8.15若M是一個有單獨的只讀輸入帶的圖靈機，w是輸入,則M在w上的格局包含狀態(tài)、工作帶和兩個讀寫頭位置。輸入w不作為M在w上的格局的一部分。如果M

在f(n)空間內(nèi)運行，w是長為n

的輸入，則M

在w

上的格局數(shù)是n2