10_第六章空間復(fù)雜度2

1、1/63,Lecture for Computation Theory,Book :《計(jì)算理論導(dǎo)引》 Introduction to the Theory of Computation Section 8.3 -8.6 PSPACE ComplexityProf : 唐常杰TangChangjie@cs.scu.edu.cn Http://teacher.scu.edu.cn/~chjtan

2、gStudents : Phd, MS in CS . 2000-- 2009, SCUStyle : Lecture / Seminar,2/63,2008.5.20 ，哀悼日第二天 ，計(jì)算理論課程 復(fù)課沉痛哀悼 汶川 8.0級(jí)地震 遇難同胞地動(dòng)天不塌 大災(zāi)有大愛(ài),3/63,作者/葉浪　　那是一張熟悉的臉 　是我痛失親人后看到的最真切的笑臉　　眼里閃著淚花 　　話里充滿著力量　

3、　那一刻 　　我感到自己有一個(gè)強(qiáng)大的祖國(guó)　　那是一張陌生的臉 　　是我埋在瓦礫下看見(jiàn)的最勇敢的臉　　撬開(kāi)了殘?jiān)?　　搬走了巨石　　那一刻 　　我感到自己有一個(gè)強(qiáng)大的祖國(guó)　　那是一張美麗的臉 　　是我躺在病床上看見(jiàn)的天使的臉　　包扎我的創(chuàng)傷 　　驅(qū)走我的恐懼　　那一刻， 　　我感到自己有一個(gè)強(qiáng)

4、大的祖國(guó),一首感人的 詩(shī)： 地動(dòng)天不塌 ，大災(zāi)有大愛(ài),4/63,那是一張慈祥的臉 　　是我奔離教室前看過(guò)的最鎮(zhèn)靜的臉　　為了自己的學(xué)生 　　成就了自己的永恒　　那一刻 　　我感到自己有一個(gè)強(qiáng)大的祖國(guó)　　那是一張年輕的臉 　　是我在排隊(duì)長(zhǎng)列里看到的最急切的臉　　為了災(zāi)區(qū)的傷員 　　獻(xiàn)出了自己的殷殷鮮血　　那一刻

5、 　　我感到自己有一個(gè)強(qiáng)大的祖國(guó)　　那是一張忙碌的臉 　　是我在救災(zāi)一線上看到的最疲憊的臉　　眼里布滿血絲 　來(lái)不及顧及自己的家人　　那一刻 　　我感到有一個(gè)強(qiáng)大的祖國(guó),5/63,那是世上最可愛(ài)的臉 　　是家鄉(xiāng)地震后不曾面見(jiàn)過(guò)的男男女女的臉　　雖遠(yuǎn)在他鄉(xiāng)海外 　　溫暖的目光卻緊緊地落在了我的身上　　那一刻

6、 　　我感到自己有一個(gè)強(qiáng)大的祖國(guó)　　地動(dòng)天不塌 　大災(zāi)有大愛(ài)　　我感到自己有一個(gè)強(qiáng)大的祖國(guó)2008年5月14日作于成都市抗震救災(zāi)指揮部作者簡(jiǎn)介　　葉浪，成都市某局副局長(zhǎng)。在成都市抗震救災(zāi)指揮部值班期間，眼見(jiàn)全民一心搶災(zāi)救災(zāi)感人場(chǎng)面，多次淚濕雙眼。他利用工作間隙，在手機(jī)上寫(xiě)下真實(shí)感 受。“在抗災(zāi)這幾天，我最強(qiáng)烈最真實(shí)的感覺(jué)，正是這首詞的題目，我相信，在強(qiáng)大祖國(guó)的支持下，我們?nèi)褚恍模?/p>

7、眾志成城，一定能夠戰(zhàn)勝災(zāi)難！”葉浪說(shuō)。,6/63,復(fù)習(xí) NPC 概念 (時(shí)間復(fù)雜類）,直 觀： NPC 即，最難纏的一群NP，他們 “拉邦結(jié)伙、互相規(guī)約、同衰共榮”, 有“繁衍能力”多倫多大學(xué)，Cook教授,1972 年 證明 3SAT in NPC3SAT作為種子，繁衍了上千個(gè)著名NPC,7/63,PSPACE-Complete CP 190,Definition 8.8: A language B is P

8、SPACE-complete if:1) B is in PSPACE, and2) For every language A?PSPACE, we have A?PB.If B merely satisfies condition 2, we say that it is PSPACE-hardThe definition is the same as NP-Complete,只緣身在此山中,B有繁衍力,只知道B有

9、繁衍力，不一定身在此山中,多項(xiàng)式時(shí)間規(guī)約,8/63,PSPACE-Complete CP 190,Definition 8.8: A language B is PSPACE-complete if:1) B is in PSPACE, and2) For every language A?PSPACE, we have A?PB.If B merely satisfies condition 2, we say th

10、at it is PSPACE-hardThe definition is the same as NP-Complete,只緣身在此山中,B有繁衍力,只知道B有繁衍力，不一定身在此山中,多項(xiàng)式時(shí)間規(guī)約,9/63,Rule for reduction,為什么沒(méi)有多項(xiàng)式空間規(guī)約？規(guī)約的目的是，以核心為種子，繁衍其他問(wèn)題所以要求規(guī)約務(wù)必做到簡(jiǎn)單A machine can explore at most one new cell

11、 at each step of its computation時(shí)間簡(jiǎn)單了，空間就簡(jiǎn)單了；空間簡(jiǎn)單了，時(shí)間未必簡(jiǎn)單？ 所以空間規(guī)約意義不大,,10/63,TQBF問(wèn)題 CP190 8.31,TQBF T –True Q –Quantifier 量詞 （for all , each ) B- Boolean F-Formula所有的變?cè)荚诹吭~的范圍內(nèi)，稱為完

12、全量化TQBF = { | is true fully quantified Boolean formula}問(wèn)題 ： TQBF成員籍判定問(wèn)題,Theorem 8.9: TQBF is PSPACE-complete,量化布爾表達(dá)式,11/63,TQBF問(wèn)題 CP190 8.31,TQBF T –True Q –Quantifier 量詞 （for all , each )

13、 B- Boolean F-Formula所有的變?cè)荚诹吭~的范圍內(nèi)，稱為完全量化TQBF = { | is true fully quantified Boolean formula}問(wèn)題 ： TQBF成員籍判定問(wèn)題,Theorem 8.9: TQBF is PSPACE-complete,問(wèn)題,結(jié)論,12/63,TQBF問(wèn)題 （CP191),證明思路： TQBF is in PSPACE（1）只緣身在

14、此山中 （只需要多項(xiàng)式空間） 將每個(gè)變量都帶入值遞歸計(jì)算公式的值（2）繁衍能力 （是 規(guī)約 的 歸宿） 書(shū)上先給了一個(gè)容易想到，但行不通的思路（CP192),13/63,證明：TQBF is in PSPACE,思想可以構(gòu)造公式 ,通過(guò)描繪接受畫(huà)面來(lái)模擬M在輸入W上的計(jì)算。因?yàn)?(1) M在W上的畫(huà)面寬度是O(Nk); (2)M可能運(yùn)行指數(shù)長(zhǎng)的時(shí)間所以：M的高度是nk的指數(shù)。但是：多項(xiàng)式歸

15、約不能產(chǎn)生指數(shù)長(zhǎng)的結(jié)果。尋找另一種新的方法(采用薩維奇定理相關(guān)技術(shù)),。,M消耗的空間,14/63,證明：TQBF is in PSPACE,1）給出一個(gè)判定TQBF多項(xiàng)式空間算法T = “on input ,a fully quantified Boolean formula” If contains no quantifiers,（即無(wú)量詞）//只能是常數(shù)T或F; { If ( it is T) acc

16、ept else reject ; }Else if ф = （存在 x）Ψ， { Ψ上遞歸地調(diào)用T，先用0換x，后用1換x。 If (其中之一T) accept ；else reject; } else if (ф =(For all x)Ψ ) { Ψ上遞歸調(diào)T，首先用0替換x，然后用1替換x。若兩個(gè)結(jié)果

17、 (因 For all ) 都是 接受，則接受；否則，拒絕。},兩次遞歸，深度<=變量個(gè)數(shù)m <=輸入長(zhǎng)度n 所以需線性空間已說(shuō)明 身在此山中 （只需要多項(xiàng)式空間）,,,15/63,證明TQBF 繁衍能力 （規(guī)約 歸宿）,Each A?PSPACE is polynomial time reduciable to TQBF,T=2,nk,開(kāi)始格局,接受格局,問(wèn)題A的計(jì)算的空間復(fù)雜度是 nk能多項(xiàng)式時(shí)間

18、規(guī)約為TQBF嗎？且看下頁(yè)分解,,,16/63,A 規(guī)約 to TQBF （歸宿）,回憶 The formula as in proof of CookLevin encodes contents of tape cells with variables 1 ～ c = |Q???{#}|each cell has one variable for each tape symbol and s

19、tateeach cell requires constant number of variableseach configuration has O(nk) cellseach configuration is encoded by O(nk) variables,17/63,TQBF問(wèn)題,C1 ,C2 ---格局 t --- 規(guī)約步數(shù), 不妨設(shè)t=2k從 簡(jiǎn)單到復(fù)雜 構(gòu)造公式 When

20、t = 1 , 􀀀 􀀀 構(gòu)造一步規(guī)約 公式， 下列兩種之一：􀀀 c1 = c2 or􀀀 c1 yields c2 in one step 􀀀 by wiring triples like CookLevin,遞歸基礎(chǔ),18/63,TQBF問(wèn)題,遞歸規(guī)律,一分為二,,,中間格局,,19/6

21、3,TQBF問(wèn)題,關(guān)鍵”從C1 格局 到 中間格局M，再到C2格局,20/63,TQBF問(wèn)題,每次遞歸將 t 一分為二，但是將公式長(zhǎng)度加倍，結(jié)果最終的公式長(zhǎng)度約為 ，所以問(wèn)題就嚴(yán)重了,費(fèi)了大力，還是指數(shù)級(jí)空間， 怎么辦？,21/63,TQBF問(wèn)題,原來(lái)的公式，一分為二后長(zhǎng)度加倍 我們引入格局變量c3, c4,將公式變換成 =,變成兩個(gè)公

22、式,,濃縮成一個(gè)公式（以時(shí)間為代價(jià)）長(zhǎng)度不翻倍了,,這里長(zhǎng)度只增加點(diǎn)線性長(zhǎng)度,,22/63,TQBF問(wèn)題,遞歸的空間消耗每層約為O(d*f(n)): 新公式的長(zhǎng)度， 遞歸深度為log( ) = O(f(n))所以空間復(fù)雜度為O(f2(n)),因?yàn)?一分為二,23/63,8.3.2 博弈的必勝策略 CP 193,博奕論-The Game Theory,日光浴者,海灘,,,,1/4,3/4,博奕論：

23、關(guān)于包含相互依存情況中理性行為 的研究。,A B兩個(gè)老板 研究小店在什么地方 生意才好，最后在中間，,24/63,棋手對(duì)弈排兵布陣 特點(diǎn)： 見(jiàn)招拆招，把握關(guān)節(jié)點(diǎn)，爭(zhēng)取主動(dòng)權(quán) 等 互博 最終分出勝負(fù) 為什么研究？ 1 游戲有了必勝策略， 玩起來(lái)沒(méi)意思了，需要修改規(guī)則 2 如果尋找必勝策略很難， 這個(gè)游戲還可以玩,博弈的必勝策略,

24、25/63,TQBF={| f是真的全量詞化布爾公式},TQBF語(yǔ)言問(wèn)題,全量詞化布爾表達(dá)式（句子）：每個(gè)變量都出現(xiàn)在某一量詞的轄域內(nèi),語(yǔ)言：所有真的全量詞化布爾表達(dá)式的集合問(wèn)題： 判定其成員籍,博弈的必勝策略,26/63,TQBF={| f是真的全量詞化布爾公式},TQBF語(yǔ)言問(wèn)題,布爾表達(dá)式：包含布爾變量、常數(shù)0,1、布爾運(yùn)算符與/或/非,全量詞化布爾表達(dá)式（句子）：每個(gè)變量都出現(xiàn)在某一量詞的轄域內(nèi),語(yǔ)言：所有真的全量詞化布爾表達(dá)

25、式的集合問(wèn)題： 判定其成員籍,博弈的必勝策略,27/63,. TQBF(真全量詞化布爾公式) 對(duì)于布爾值變量，值域?yàn)椋?,1｝的公式， 總能找到相應(yīng)的變量取值，使其語(yǔ)句結(jié)果=TRUE，。,博弈的必勝策略,尋求一種策略，見(jiàn)招拆招，最終獲勝,,怎樣聯(lián)系起來(lái)？,,人的智力對(duì)抗,邏輯描述,,28/63,量化語(yǔ)句? 博弈 作用:描述和解釋該語(yǔ)

26、句的含義博弈? 量化語(yǔ)句 作用:理解該博弈的復(fù)雜性,博奕和量化語(yǔ)句緊密相關(guān),29/63,E.g. 前束范式的量詞化布爾公式 f=$x1"x2$x3…Qxk[?] Q:$/"， ?--去掉量詞的公式 f與下面的博弈關(guān)聯(lián) 2名選手A, E，輪流為x1，x2，x3…xk選值

27、 容易記憶的規(guī)定： 選手A對(duì)應(yīng)" , 選手 E對(duì)應(yīng) $,量化語(yǔ)句 ?博弈,,量詞集中在前面,30/63,選手E所對(duì)應(yīng)的量詞,選手A所對(duì)應(yīng)的量詞,選手E取值,選手A取值,對(duì)變量進(jìn)行處理的語(yǔ)句,TRUE: E先勝FALSE: A勝,輪流出招,博弈的必勝策略 CP191,Q某量詞（不知道K的奇偶性,31/63,不含量詞的公式,TRUE: E先勝FALSE: A勝,輪流出招

28、,博弈的必勝策略 CP191,Q某量詞（不知道K的奇偶性,32/63,E.g8.9 f1=$x1"x2$x3[(x1Úx2)Ù(x2Úx3)Ù(x1Úx3)],E確定的變量值,,,A確定的變量值,,?1,設(shè)E：x1=1/0;A：x2=0;E：x3=1/0; ?=0,A贏,A必勝：,f2=$x1"x2$x3[(x1Úx2)Ù(x2Úx3

29、)Ù(x2Úx3)],?2,必勝策略選手有必勝策略，如果他在博弈雙方都下出最關(guān)鍵步驟時(shí)能贏,博弈的必勝策略 CP193,,,33/63,好消息判定在與某具體公式關(guān)聯(lián)的公式博弈中哪方有必勝策略的問(wèn)題是PSPACE完全的 說(shuō)明尋找必勝策略很難，游戲還可以玩令FORMULA-GAME= {|在與?關(guān)聯(lián)的公式博奕中哪一方有必 勝策略的問(wèn)題} 問(wèn)題：判定成員籍,博弈的必勝策略

30、 CP193,34/63,定理8.10 FORMULA-GAME是PSPACE完全的,Proof思路： FORMULA-GAME 等價(jià)于 TQBF下頁(yè)是詳細(xì)證明,博弈的必勝策略,35/63,Proof: f1=$x1"x2$x3…[?]是TRUE的條件： $x1"x2$x3, ?=TRUE E（先手）必勝策略的條件：E給x1賦某值

31、，使得對(duì)x2任意賦值，E可以給x3賦一個(gè)值，（E第二制勝）使得?=TRUE若f2="x1,x2, x3$x4 , x5 "x6 [?]A先給x1,x2, x3賦值；E再給x4,x5賦值，A再給x6賦值，使得?=FALSE∴ 當(dāng)f1 ∈FORMULA-GAME ，即有必勝策略，f1 ∈TQBF成立∴ FORMULA-GAME=TQBF 根據(jù)定理8.8：TQBF是PSPACE完全的（ 直觀感覺(jué)：比N

32、PC還要難）∴FORMULA-GAME是PSPACE完全的說(shuō)明尋找 必勝策略很難，游戲還可以玩,P188,博弈的必勝策略,E先手 的游戲,A先手 的游戲,36/63,一種兒童游戲 選手輪流給世界各地的城市命名 每一座選中的城市的首字母必須與前一座城市的尾字母相同，不得重復(fù)。游戲從某指定的起始城市開(kāi)始，以某方無(wú)法延續(xù)而認(rèn)輸為止。E.g. 開(kāi)始： Peoria Peoria?Amherst?Tucson?

33、Nashua… 結(jié)束：直到某方被難倒類似成語(yǔ)接龍： 大地回春—春滿人間—間不容發(fā)-發(fā)展才是硬道理 –理直氣壯--….( 不得重復(fù)),廣義地理學(xué) (GG ) CP194,37/63,類似成語(yǔ)接龍,節(jié)點(diǎn)是世界各地的城市,廣義地理學(xué) 有向圖表示,38/63,按照地理學(xué)規(guī)則翻譯為圖表示法選手 指定起始節(jié)點(diǎn) , 交替地挑選節(jié)點(diǎn), 形成簡(jiǎn)單路徑.要求是簡(jiǎn)單路徑,(每節(jié)點(diǎn)只用1次,不重復(fù).第1個(gè)犯規(guī)或不能擴(kuò)展路徑

34、 的選手 輸.,廣義地理學(xué) CP194,39/63,1,3,1,1,2,,,,選手I可以選節(jié)點(diǎn)2，3選手2 再無(wú)對(duì)策,選手I必勝 可選空間 很重要,廣義地理學(xué) CP194,40/63,1,3,,選手I選節(jié)點(diǎn)3選手2 再無(wú)對(duì)策,選手I必勝 可選空間 很重要,廣義地理學(xué),41/63,1,3,1,1,5,,,節(jié)點(diǎn)3，選手II只有1條路徑可選，即節(jié)點(diǎn)5選手2 再無(wú)對(duì)策,選手I必勝,廣義地理學(xué),42/63,1,3,

35、1,1,5,,,選手II，只能選節(jié)點(diǎn)3 此后 ，選手2 再無(wú)對(duì)策,選手I必勝,廣義地理學(xué),43/63,1,3,6,1,1,5,8,,,,,,,從節(jié)點(diǎn)5出發(fā)，選手I，可以選節(jié)點(diǎn)6，7，8,7,,選手I必勝,廣義地理學(xué),44/63,1,3,6,1,1,5,,,,,選手I，選擇節(jié)點(diǎn)6此后 ，選手2 再無(wú)對(duì)策,選手I必勝,廣義地理學(xué),規(guī)定的始點(diǎn),選手1,選手2,45/63,1,3,6,1,1,5,,,,,選手I，選擇節(jié)點(diǎn)6此后 ，選手2

36、再無(wú)對(duì)策,選手I必勝,廣義地理學(xué),規(guī)定的始點(diǎn),選手1,選手2,46/63,1,3,6,1,1,5,,,,,選手I，選擇節(jié)點(diǎn)6此后 ，選手2 走投無(wú)路,選手I必勝,廣義地理學(xué),規(guī)定的始點(diǎn),選手1,選手2,47/63,廣義地理學(xué) (GG ),選手I必勝,1,3,6,4,5,2,,7,8,9,,,,,,,,,,,,,,,,,從節(jié)點(diǎn)1開(kāi)始，選手I先做選擇,1-1,2-1,1-2,48/63,1,3,6,4,5,2,,7,8,9,,,,,,,,

37、,,,,,,,,,1,游戲這里修改了方向變成節(jié)點(diǎn)3?節(jié)點(diǎn)6,廣義地理學(xué)， 修改 圖 選手II必勝,,2,1,2 選1的滑鐵盧,,,,49/63,Good News定理8.11 判定在廣義地理學(xué)中某方有必勝策略的問(wèn)題是PSPACE完全的定理的意義 說(shuō)明這個(gè)游戲 難找必勝策略， 還有趣味令GG= {|在圖G上以節(jié)點(diǎn)b起始的廣義地理學(xué)游戲中，選手I有必勝策略} 問(wèn)題 成員籍判定,廣義地理學(xué),50/63,定

38、理8.11 GG是PSPACE完全的 //問(wèn) 選手I是否有必勝策略Proof：（1）只緣身在此山中 （只需要多項(xiàng)式空間）輸入： ＜G，b＞，G是有向圖，b是指定的開(kāi)始節(jié)點(diǎn)：輸出： Yes/No1) it (b出度為0) reject ; // 選手I 走投無(wú)路。2 棧中記b的子節(jié)點(diǎn)b1，b2，…，bk，刪b 及關(guān)聯(lián)箭頭．得新圖G1 3 對(duì)子節(jié)點(diǎn)＜G1，bi＞遞歸//遞歸分支小于節(jié)點(diǎn)總數(shù)N)4)if (all 遞

39、歸分支接受)，選手Ⅱ有必勝策略，拒絕。 else 選手Ⅱ無(wú)必勝策略，而選手I有必勝策略，接受。算法僅需 遞歸?？臻g。遞歸每層在棧中添加一個(gè)節(jié)點(diǎn)，最多m層，m是G的節(jié)點(diǎn)數(shù)。因此算法在線性空間內(nèi)運(yùn)行。,廣義地理學(xué),51/63,Proof：（1）只緣身在此山中 （只需要多項(xiàng)式空間）輸入： ＜G，b＞，G是有向圖，b是指定的開(kāi)始節(jié)點(diǎn)：輸出： Yes/No1) it (b出度為0) reject ; // 選手1 走投無(wú)路。

40、2 棧中記b的子節(jié)點(diǎn)b1，b2，…，bk，刪b 及關(guān)聯(lián)箭頭．得新圖G1 3 對(duì)子節(jié)點(diǎn)＜G1，bi＞遞歸 //遞歸分支小于節(jié)點(diǎn)總數(shù)N)4)if (all 遞歸分支接受)，選手Ⅱ有必勝策略，拒絕。 else 選手Ⅱ無(wú)必勝策略，而選手I有必勝策略，接受。注意：1 多個(gè)遞歸分支 不同時(shí)作，只用一份?？臻g（空間復(fù)用） 2 每次遞歸 在棧中 加一個(gè)節(jié)點(diǎn)，最多m層，m是節(jié)點(diǎn)總數(shù)結(jié)論 算法在線性空間內(nèi)運(yùn)行。,

41、廣義地理學(xué),52/63,Proof（2）證GG的PSPACE難解性 （規(guī)約的歸宿）FORMULA-GAME f=$x1"x2$x3… Qxk[?]($開(kāi)頭和結(jié)尾, $/"交替) ?廣義地理學(xué)的實(shí)例 選手I---選手E （用存在量詞 Exist） 選手II—選手A （用全稱量詞 All ),廣義地理學(xué) 定理8.11 （續(xù)）,,多項(xiàng)式時(shí)間歸

42、約,不妨 設(shè) E先手， E結(jié)尾)、（簡(jiǎn)單，不影響實(shí)質(zhì)）,定理8.10 已證明是 PSpace完全的,GG,53/63,Proof（2）證GG的PSPACE難解性 （規(guī)約的歸宿）FORMULA-GAME 公式博弈 f=$x1"x2$x3… Qxk[?]($開(kāi)頭和結(jié)尾, $/"交替) ?廣義地理學(xué)的實(shí)例 選手I---選手E （用存在量詞 Exist）

43、 選手II—選手A （用全稱量詞 All ),廣義地理學(xué) 定理8.11 （續(xù)）,,多項(xiàng)式時(shí)間歸約,定理8.10 已證明是 PSpace完全的,合取范式 且不妨 設(shè) E先手， E結(jié)尾)、（可加啞變量實(shí)現(xiàn)）（簡(jiǎn)單，不影響實(shí)質(zhì)）,54/63,指定始點(diǎn),,,變量,選手I-------選手E,對(duì)應(yīng)于,路徑對(duì)應(yīng)變量的賦值,公式博弈?的地理學(xué)圖,不妨 設(shè) E先手E結(jié)尾,輸入T開(kāi)始,每個(gè)分支點(diǎn)左真 右假,55/63,,選手I---

44、--選手II------,,,選手II-------選手A,對(duì)應(yīng)于,路徑對(duì)應(yīng)變量的賦值,模擬公式博弈的地理學(xué)圖 CP195,A無(wú)多余選擇,E 選擇這條,56/63,,選手I-----選手II------,,,選手II-------選手A,對(duì)應(yīng)于,,,路徑對(duì)應(yīng)變量的賦值,模擬公式博弈的地理學(xué)圖,如此這般…,到了最后.博弈結(jié)束。公式結(jié)果為T. E勝（選手1）否則A勝下頁(yè)解釋,因已假定最后1個(gè)量詞是存在量詞，等A在C走下一步

45、下頁(yè)解釋,57/63,模擬公式博弈的地理學(xué)圖,選手I選擇文字,,,,,c1,c2,cm,,,,,,選手2在C點(diǎn)的選擇 其中之一 比方Ci,設(shè)選手2在C點(diǎn)可選擇的公式中的字句Ci,,,58/63,模擬公式博弈的地理學(xué)圖,選手II選擇Ci,選手I選擇文字,,,,,c1,c2,cm,,,,,,,,注意 一樣,,,,59/63,模擬公式博弈的地理學(xué)圖,選手II選擇Ci,選手I選擇文字,,,,,c1,c2,cm,,,,,,有上橫線的連接右邊

46、,無(wú)上橫線的連左邊,,,60/63,模擬“若公式=FALSE，按公式博弈，應(yīng) A （選手2）勝”,選手II選擇Ci,,,,,c1,c2,cm,,,,,,2 有上橫線的連接右邊 ，選手1只能選擇False ,失敗,,,,1 公式f中肯定有不滿足的子句 可選選手2 選擇它,,61/63,模擬“若公式=TRUE，按公式博弈，應(yīng) A （選手2）敗”,選手II選擇Ci,,,,,c1,c2,cm,,,,,,無(wú)上橫線的連接右邊 ，選手1只能選擇Tr

47、ue ,勝利,,,,1 公式f中肯定有一定滿足的子句 可選 選手2 選擇它,,,62/63,前兩頁(yè) 說(shuō)明 地理學(xué)圖 很好地 模擬了公式博弈小結(jié) 前面 14 頁(yè)面定理8.11 GG是PSPACE完全的 //問(wèn) 選手I是否有必勝策略Proof 要點(diǎn)： （1）只緣身在此山中 （只需要多項(xiàng)式空間） （2）證GG的PSPACE難解性 （規(guī)約的歸宿）,模擬公式博弈的地理學(xué)圖,63/63,Any Question