計算理論16難解性

1、2022-1-26SCU CS Computation1Chap 9 難解性 可以從下列文件獲得素材：可以從下列文件獲得素材：難解性難解性素材素材.doc2022-1-26SCU CS Computation2難解性的含義：難解性的含義： 若某一計算問題在理論上是可若某一計算問題在理論上是可解的，但解法需要耗費大量的時解的，但解法需要耗費大量的時間或空間，以至于無法在實踐中間或空間，以至于無法在實踐中應(yīng)用，則稱該問題是難解的。應(yīng)用，則稱該問題是難解的。2022-1-26SCU CS Computation3難解性的形式難解性的形式難解性可以有多種形式：難解性可以有多種形式：例如例如 ： 1、一

2、個大部分時間容易計算但偶爾、一個大部分時間容易計算但偶爾很難算的問題，僅在最壞情況下是難解很難算的問題，僅在最壞情況下是難解的；的； 2、在超級計算機(jī)上是易算的，但在、在超級計算機(jī)上是易算的，但在PC機(jī)上可能需要過量時間的問題機(jī)上可能需要過量時間的問題2022-1-26SCU CS Computation4本章的目標(biāo)本章的目標(biāo) 證明存在理論上可判定證明存在理論上可判定但實際中不可判定的問題即但實際中不可判定的問題即可判定而難解的問題。可判定而難解的問題。2022-1-26SCU CS Computation5 總之：難解性問題指的是在最壞情總之：難解性問題指的是在最壞情況下復(fù)雜性太大，以至于在

3、任何所能想況下復(fù)雜性太大，以至于在任何所能想象建造出來的計算機(jī)上所耗費的時間都象建造出來的計算機(jī)上所耗費的時間都將超過宇宙的余生。將超過宇宙的余生。 例如：例如：SAT問題和所有的問題和所有的NP完全問完全問題。題。2022-1-26SCU CS Computation69.1 層次定理層次定理 層次定理的含義：定理中的每一個都能證明時層次定理的含義：定理中的每一個都能證明時間和空間復(fù)雜性類不全相同，它們形成了一個層次間和空間復(fù)雜性類不全相同，它們形成了一個層次結(jié)構(gòu)，其中時空界限較大的類比時空界限較小的類結(jié)構(gòu)，其中時空界限較大的類比時空界限較小的類包含更多的語言。包含更多的語言。 例如：層次定

4、理能形式化的證明：圖靈機(jī)在更例如：層次定理能形式化的證明：圖靈機(jī)在更多的時間或空間能擴(kuò)大它所能解的問題類。也就是多的時間或空間能擴(kuò)大它所能解的問題類。也就是說，圖靈機(jī)在時間說，圖靈機(jī)在時間n3 內(nèi)比內(nèi)比n2內(nèi)能判定更多的語言。內(nèi)能判定更多的語言。2022-1-26SCU CS Computation7層次定理的分類層次定理的分類n空間復(fù)雜性層次定理（簡單）（簡單）n時間復(fù)雜性層次定理（復(fù)雜）（復(fù)雜） 2022-1-26SCU CS Computation8函數(shù)函數(shù) f:N N,f(n) =logn 稱為空間可稱為空間可構(gòu)造的，如果函數(shù)把構(gòu)造的，如果函數(shù)把1n（n個個1的字符串）的字符串） 映射

5、為映射為f(n)的二進(jìn)制表示，并在空間的二進(jìn)制表示，并在空間O(f(n)內(nèi)是可計算的。內(nèi)是可計算的。 含義：如果存在某個圖靈機(jī)含義：如果存在某個圖靈機(jī)M，在在O(f(n)空間內(nèi)運行，并且在輸入空間內(nèi)運行，并且在輸入1n后總能后總能停機(jī)，停機(jī)時停機(jī)，停機(jī)時f(n)的二進(jìn)制表示出現(xiàn)在帶子的二進(jìn)制表示出現(xiàn)在帶子上，則上，則f是空間可構(gòu)造的是空間可構(gòu)造的定義9.12022-1-26SCU CS Computation9 通常出現(xiàn)的不小于通常出現(xiàn)的不小于logn的函數(shù)都是空的函數(shù)都是空間可構(gòu)造的，例如間可構(gòu)造的，例如logn ，nlogn ，n2. . n2是空間可構(gòu)造的，因為機(jī)器以是空間可構(gòu)造的，因為

6、機(jī)器以1 1n為輸為輸入，通過數(shù)入，通過數(shù)1 1的數(shù)目得到的數(shù)目得到n的二進(jìn)制形式，的二進(jìn)制形式，采用標(biāo)推的方法將采用標(biāo)推的方法將n自乘，輸出。全部空間自乘，輸出。全部空間消耗是消耗是O( (n) )，當(dāng)然也是，當(dāng)然也是O( (n2) ) 。 例9.22022-1-26SCU CS Computation10定理9.3 空間層次定理 對任何空間可構(gòu)造函數(shù)對任何空間可構(gòu)造函數(shù)f:N N，存在語言存在語言A，在空間在空間O（f（n）內(nèi)可判內(nèi)可判定，但不能在空間定，但不能在空間o（f（n） 證明思路證明思路 必須顯示一個語言必須顯示一個語言A具有具有兩個性質(zhì)：第一，兩個性質(zhì)：第一，A在空間在空間O（

7、f（n）內(nèi)可判定；第二，內(nèi)可判定；第二，A不能在空間不能在空間o（f（n）判定。判定。2022-1-26SCU CS Computation11 推論9.4 空間層次定理 對任何兩個函數(shù)對任何兩個函數(shù)f1 ， f2：N N,其中其中f1（n）等于等于o（f2（n），）， f2是空間可構(gòu)是空間可構(gòu)造的，有造的，有SPACE（f1（n）真包含于真包含于SPACE（f2（n） 該推論的作用能夠把不同的空間復(fù)雜該推論的作用能夠把不同的空間復(fù)雜性類分開。性類分開。2022-1-26SCU CS Computation12 推論9.5 對任意兩個實數(shù)對任意兩個實數(shù)0r1 r2, ,有有SPACE(n r1

8、)真包含于真包含于SPACE(n r2)也可以用空間層次定理來分離前也可以用空間層次定理來分離前面碰到的的兩個空間復(fù)雜性類。面碰到的的兩個空間復(fù)雜性類。2022-1-26SCU CS Computation13 推論9.6 NLNL真包含于真包含于PSPACEPSPACE證明：薩維奇定理說明證明：薩維奇定理說明NL不真包含于不真包含于SPACE(2n ),空間層次定理說明空間層次定理說明SPACE(2n )真包含于真包含于SPACE(n), ,所以推所以推論成立。論成立。 2022-1-26SCU CS Computation14 推論9.7 PSPACEPSPACE真包含于真包含于EXPSP

9、ACEEXPSPACE 意義：判定過程必須消耗多于多項式意義：判定過程必須消耗多于多項式的空間。的空間。2022-1-26SCU CS Computation15 定義9.8函數(shù)函數(shù) t:N N,t(n) =nlogn 稱為時間可稱為時間可構(gòu)造的，如果函數(shù)把構(gòu)造的，如果函數(shù)把1 1n（n個個1 1的字符串）的字符串） 映射為映射為t(n)的二進(jìn)制表示，并在時間的二進(jìn)制表示，并在時間O(t(n)內(nèi)是可計算的。內(nèi)是可計算的。 含義：如果存在某個圖靈機(jī)含義：如果存在某個圖靈機(jī)M，在時在時間間O(t(n)內(nèi)運行，而且在輸入內(nèi)運行，而且在輸入1 1n上啟動后上啟動后總能停機(jī)，停機(jī)時總能停機(jī)，停機(jī)時t(n

10、)的二進(jìn)制表示出現(xiàn)的二進(jìn)制表示出現(xiàn)在帶子上，則在帶子上，則t是時間可構(gòu)造的。是時間可構(gòu)造的。2022-1-26SCU CS Computation16 通常出現(xiàn)的不小于通常出現(xiàn)的不小于nlogn的函數(shù)都是時的函數(shù)都是時間可構(gòu)造的，例如間可構(gòu)造的，例如nlogn ， , ,n2 2以及以及2 2n 。 是時間可構(gòu)造的，首先設(shè)計一個是時間可構(gòu)造的，首先設(shè)計一個TM，以二進(jìn)制計算以二進(jìn)制計算l l的個數(shù)。為此該的個數(shù)。為此該TM沿著帶子移動沿著帶子移動一個二進(jìn)制計數(shù)器，每到一個輸入位置就把它加一個二進(jìn)制計數(shù)器，每到一個輸入位置就把它加1，直至輸入的末端。因為對于，直至輸入的末端。因為對于n個輸入位置

11、的每個輸入位置的每一個都需要消耗一個都需要消耗O(logn)步，所以這部分工作消步，所以這部分工作消耗耗O(nlogn)步。然后，從步。然后，從n的二進(jìn)制表示中計算的二進(jìn)制表示中計算出的出的 二進(jìn)制形式。因為涉及的數(shù)的長度是二進(jìn)制形式。因為涉及的數(shù)的長度是O(logn) ，所以任何合理的計算方法都將消耗時，所以任何合理的計算方法都將消耗時間間O(nlogn) 。 例9.9n nn nn n2022-1-26SCU CS Computation17定理9.10 時間層次定理 對于任何時間可構(gòu)造函數(shù)對于任何時間可構(gòu)造函數(shù)t:N N，存在語言存在語言A，在時間在時間O（t（n）內(nèi)可判定，內(nèi)可判定，但

12、在時間但在時間o（t（n）/logt(n)內(nèi)不可判定內(nèi)不可判定 證明思路證明思路 類似類似10.310.3。2022-1-26SCU CS Computation18 推論9.11 對任何兩個函數(shù)對任何兩個函數(shù)t1 ， t2：其中其中t1（n）等于等于o(t2（n）/logt2 (n)， t2是時間可是時間可構(gòu)造的，有構(gòu)造的，有TIME(t1（n）)真包含于真包含于TIME(t2（n）)。 2022-1-26SCU CS Computation19 推論9.12 對任意兩個實數(shù)對任意兩個實數(shù)0r1 r2 , 有有TIME(n r1 )真包含于真包含于SPACE(n r2 )2022-1-26S

13、CU CS Computation20 推論9.13P真包含于真包含于EXPTIME2022-1-26SCU CS Computation21指數(shù)空間完全性指數(shù)空間完全性證明一個具體的語言事實難解需要分兩步：證明一個具體的語言事實難解需要分兩步： 第一：圖靈機(jī)在第一：圖靈機(jī)在EXPSPACE內(nèi)比在內(nèi)比在PSPACE內(nèi)判定更多的語言；內(nèi)判定更多的語言； 第二：證明有關(guān)廣義正則表達(dá)式的一第二：證明有關(guān)廣義正則表達(dá)式的一個具體的語言是個具體的語言是EXPSPACE完全的，即不完全的，即不能在多項式時間、也不能在多項式空間內(nèi)能在多項式時間、也不能在多項式空間內(nèi)判定。判定。2022-1-26SCU CS

14、 Computation22定義定義9.149.14語言語言B是是EXPSPACE完全的，當(dāng)且僅當(dāng)：完全的，當(dāng)且僅當(dāng)： （1）B EXPSPACE;并且并且 （2）EXPSPACE中的每個中的每個A都是多項都是多項式時間可歸約到式時間可歸約到B。2022-1-26SCU CS Computation23廣義正則表達(dá)式廣義正則表達(dá)式 正則表達(dá)式是正則表達(dá)式是， 以及字母表中的符以及字母表中的符號經(jīng)過有限次正則運算（并、連接和星）得號經(jīng)過有限次正則運算（并、連接和星）得到的表達(dá)式。到的表達(dá)式。 廣義正則表達(dá)式是允許指數(shù)運算（廣義正則表達(dá)式是允許指數(shù)運算（）的正則表達(dá)式。的正則表達(dá)式。Rk = Rk

15、 = R R REQREX =|Q和和R是等價的廣義是等價的廣義正則表達(dá)式正則表達(dá)式k2022-1-26SCU CS Computation24定理定理9.159.15EQREX 是是EXPSPACE完全的。完全的。 證明思路：在度量判定證明思路：在度量判定 EQREX 的復(fù)雜性的復(fù)雜性時，假設(shè)所有指數(shù)都寫成二進(jìn)制整數(shù)。表時，假設(shè)所有指數(shù)都寫成二進(jìn)制整數(shù)。表達(dá)式的長度是它包含的所有符號的總數(shù)。達(dá)式的長度是它包含的所有符號的總數(shù)。2022-1-26SCU CS Computation25.2 相對化2022-1-26SCU CS Computation261. 研究的主要的內(nèi)容給出有力證據(jù)否定用

16、對角化法解決給出有力證據(jù)否定用對角化法解決P與與NP問題的可能性問題的可能性.2022-1-26SCU CS Computation272. 幾個基本概念和定義(1)諭示 （可比喻為 一塊 超級芯片 ， 外星人的智能禮物） P138:語言B的一個諭示是一個能夠報告某個串是否為B的成員的外部裝置. 一個諭示是一個語言A.(2)諭示圖靈機(jī)MA是通常的圖靈機(jī)附加一條諭示帶, 每當(dāng)M在諭示帶上寫下一個字符串時,就能在一步計算內(nèi)得知這個字符串是否屬于A.2022-1-26SCU CS Computation282. 幾個基本概念和定義(續(xù))(3)PA采用諭示A的多項式時間諭示圖靈機(jī)可判定的語言類.(4)

17、NPA采用諭示A的非確定多項式時間諭示圖靈機(jī)可判定的語言類.2022-1-26SCU CS Computation293. 舉例(1)NPP(1)NPPSATSAT 含義含義: :相對于可滿足性問題的多項式時間計相對于可滿足性問題的多項式時間計算包含了算包含了NPNP問題的全部問題的全部. .(2)(2)COCONP PNP PSATSAT(3)(3)極小公式極小公式: :如果一個公式?jīng)]有更小的公式與如果一個公式?jīng)]有更小的公式與之等價之等價, ,則稱它為極小的則稱它為極小的. .2022-1-26SCU CS Computation30NONMIN-FORMULA=NONMIN-FORMULA

18、=| 不是極小布爾公式不是極小布爾公式 NP OR NP? NPSAT(1)等價問題屬于等價問題屬于CONP(2)諭示諭示SAT檢查是否有檢查是否有更小的等價公式更小的等價公式.是則接是則接受受.2022-1-26SCU CS Computation314. 對角化方法的局限(1)對角化方法的核心:是一臺圖靈機(jī)對另一臺圖靈機(jī)的模擬.(2)結(jié)論:凡是僅用對角化方法證明的關(guān)于圖靈機(jī)的定理,當(dāng)給兩臺機(jī)器以相同諭示的時候,仍然成立.2022-1-26SCU CS Computation32問題n 能否用對角化方法證明P與NP不同,亦即它們相對于任何諭示都不同? n能否依據(jù)簡單的模擬證明說明P與NP相等

19、,即證明它們對于任何諭示都是相等的?2022-1-26SCU CS Computation331) 存在諭示A使得PA NPA2) 存在諭示B使得PB = NPB上述定理表明不太可能用對角化方法和簡單模擬的證明來解決P與NP問題.2022-1-26SCU CS Computation34證明思路證明思路(2)只要令B是PSPACE完全問題如TQBF即可. NPTQBFNPSPACE PSPACE PTQBF因為可以把非確定型多項式時間諭示機(jī)器轉(zhuǎn)變?yōu)榉谴_定型多項式空間機(jī)器.薩維奇定理因為TQBF是PSAPCE完全的.2022-1-26SCU CS Computation35 構(gòu)造諭示A.設(shè)計A使

20、得NPA中的某個語言LA可以證明需要蠻力搜索,因而LA不可能屬于PA.因此可以得出PANPA的結(jié)論. LA=|x A |x| = | NPA PA2022-1-26SCU CS Computation36關(guān) 鍵n構(gòu)造諭示A: 經(jīng)過所有構(gòu)造步驟以后狀態(tài)沒有確定下來的字符串聲明為不在A中.亦即沒有多項式時間諭示機(jī)器能夠以諭示A判定LA.2022-1-26SCU CS Computation379.3 電路復(fù)雜性電路復(fù)雜性2022-1-26SCU CS Computation38布爾電路布爾電路n定義.20 n布爾電路是由導(dǎo)線連接的門和輸入的集合。n門的三種形式：與、或、非門n布爾函數(shù)：AND、OR

21、、NOTn門：布爾函數(shù)處理器輸入輸出2022-1-26SCU CS Computation39布爾電路示例布爾電路示例x1輸出門x2x3輸入變量0 x1輸出1x20 x3輸入100111用函數(shù)描述布爾電路的輸入/輸出：Fc:0,1n-0,1Fc(a1,an)=b2022-1-26SCU CS Computation40例例9.21 奇偶函數(shù)奇偶函數(shù)parityn:0,1n-0,1輸出輸出1，當(dāng)且僅當(dāng)輸入變，當(dāng)且僅當(dāng)輸入變量中有奇數(shù)個量中有奇數(shù)個1x1x2x3x4實現(xiàn)例10.21 布爾電路2022-1-26SCU CS Computation41電路族電路族n定義9.22 n一個電路族C是電路的

22、一個無窮列表（C0， C1， C2，), 其中Cn有n個輸入變量。n稱C在0，1上判定語言A，如果對于每個字符串w，wA 當(dāng)且僅當(dāng)Cn(w)=1,其中n是w的長度。n電路的規(guī)模-所包含門的數(shù)目n規(guī)模復(fù)雜度：一個電路族（C0， C1， C2，)的規(guī)模復(fù)雜度是一個函數(shù)f:N-N, 其中f(n)是Cn的規(guī)模n深度及復(fù)雜度：電路的深度是從輸入變量到輸出門的最長路徑的長度。n規(guī)模極小、深度極小2022-1-26SCU CS Computation42電路復(fù)雜度電路復(fù)雜度n定義9.23 n語言的電路規(guī)模復(fù)雜度是該語言的極小電路族的規(guī)模復(fù)雜度。n語言的電路深度復(fù)雜度是該語言的極小電路族的深度復(fù)雜度。2022

23、-1-26SCU CS Computation43定理定理9.25 cp212n定理10.25設(shè)t:N-N是一個函數(shù)，t(n) n。若 ，則A的電路復(fù)雜度為 。n時間復(fù)雜度小的語言，電路復(fù)雜度也小)( ntTimeA)(2ntO2022-1-26SCU CS Computation44證明思路證明思路nM是在時間t(n)內(nèi)判定A的TM。對每個n，構(gòu)造電路Cn模擬M在長為n的輸入上的運算。nCn的門分成行，每一行對應(yīng)M進(jìn)行運算的一個格局。每一行用導(dǎo)線連到上一行，指示從上一行的格局能夠計算得到自己的格局。n修改M使得輸入編碼為0，1。nM在進(jìn)入接收狀態(tài)之前，把讀寫頭移到最左單元，寫下空格符號。這樣

24、就可以指定電路的最后一行的一個門為輸出門。2022-1-26SCU CS Computation45證明證明M在輸入w上的畫面定義起始格局第二個格局第t(n)個格局Cell1,1Cellt(n),1（接受位置） 狀態(tài)和讀寫頭下的符號表示為一個單一的復(fù)合字符。 通過察看cellt(n),1，就能確定M是否已經(jīng)接受。 每一單元的內(nèi)容都由上一行的某些單元來決定。 celli-1,j-1,celli-1,j,celli-1,j+1-celli,j2022-1-26SCU CS Computation46 構(gòu)造電路Cn對應(yīng)畫面的每一個單元有多個門，添加燈表示某些門的輸出。對于畫面的每個單元有k盞燈(k是

25、U(XQ)中元素的數(shù)目)。總共kt(n)2盞燈。燈表示為：一個單元只能有一盞燈開著，如果lighti,j,s開著，celli,j就包含符號s。通過考察轉(zhuǎn)移函數(shù)，可以確定影響celli,j的三個單元的哪些賦值會使celli,j包含s。)(),(,1 ,Qsntjisjilight2022-1-26SCU CS Computation4701010101v一盞燈的電路2022-1-26SCU CS Computation48特殊處理1 畫面左邊界和右邊界的單元,只有上一行的兩個單元可能影響它的內(nèi)容，修改電路，模擬這種情況。2 第一行的單元對應(yīng)起始格局，它們的燈用導(dǎo)線連到輸入變量。這些單元的值是由輸

26、入字符串w決定的。Light1,1,q01-w1 light1,1, q00- -w1Light1,2,1-w2 light1,2,0- -w2 light1,n,1-wn light1,n,0- -wn第一行中剩余單元對應(yīng)帶子上初始值為空的位置的燈亮。3指定輸出門為與lightt(n),1,qaccept相關(guān)聯(lián)的門。2022-1-26SCU CS Computation49定理定理9.26 cp215n布爾電路是可滿足的，如果輸入的某一賦值使電路布爾電路是可滿足的，如果輸入的某一賦值使電路輸出輸出1。n電路可滿足性問題電路可滿足性問題CIRCUIT-SAT=|C是可滿足的布爾電路是可滿足的布爾電路n定理定理10.26 CIRCUIT-SAT是是NP完全的。完全的。n1 證明證明CIRCUIT-SAT屬于屬于NPn這是顯然的，因為非確定型多項式時間圖靈機(jī)這是顯然的，因為非確定型多項式時間圖靈機(jī)很容易驗證電路是否是可滿足的。很容易驗證電路是否是可滿足的。 2022-1-26SCU CS Computation502 證明NP中的任何語言A可