算法分析與設(shè)計(jì)-2016-第4講.ppt

算法分析與設(shè)計(jì),第4講-2016 山東大學(xué)計(jì)算機(jī)學(xué)院/軟件學(xué)院,上次內(nèi)容： (1)確定型圖靈機(jī)與P類(lèi)，DTM多項(xiàng)式時(shí)間可解的-P類(lèi) (2)非確定圖靈機(jī)與NP類(lèi)，NP類(lèi)-多項(xiàng)式時(shí)間可驗(yàn)證的，或NTM多項(xiàng)式時(shí)間可計(jì)算的。 注意：在定義時(shí)空復(fù)雜性時(shí)， 我們只關(guān)心NTM程序計(jì)算回答為Yes的實(shí)例的時(shí)空復(fù)雜性。 回答否的實(shí)例不關(guān)心。 只是針對(duì)那些回答為Yes的實(shí)例定義時(shí)空復(fù)雜性， 這樣定義足以滿足我們的需要。 Rabin與Scott兩個(gè)人最先在IBM做的工作，最先定義的非確定計(jì)算。 企圖把算法分為兩大類(lèi)，多項(xiàng)式時(shí)間的和指數(shù)時(shí)間的， 其實(shí)這樣分類(lèi)是有局限性的，不一定完美，但能說(shuō)明問(wèn)題。,相隔了近30年！ 非確定圖靈機(jī)沒(méi)法實(shí)現(xiàn)！,因?yàn)榕卸▎?wèn)題都可以當(dāng)作一個(gè)語(yǔ)言的識(shí)別問(wèn)題。一個(gè)語(yǔ)言：給定符號(hào)集=0，1，一個(gè)語(yǔ)言就是一個(gè)*的子集L *。 判定一個(gè)x *是否屬于L，即所謂判定問(wèn)題。,只能驗(yàn)證一面,，SAT實(shí)例符號(hào)集合 L，回答是的SAT實(shí)例集合 判定：x *，是否屬于L,1變換到2，應(yīng)該達(dá)到的目的：若2存在多項(xiàng)式算法， 則1也有多項(xiàng)式算法。 多項(xiàng)式變換(歸約)： 1=；2= 變換f：1* 2* IL1，f(I)L2，1(I)=2(f(I) f變換可以在p(|I|=n)時(shí)間內(nèi)計(jì)算完成。 則f稱(chēng)為由1到2的多項(xiàng)式時(shí)間歸約。Reduction,(1)非確定型圖靈機(jī)與驗(yàn)證機(jī)還是不同的。 (2)但是有一個(gè)結(jié)論：一個(gè)問(wèn)題是多項(xiàng)式時(shí)間可驗(yàn)證的， 當(dāng)且僅當(dāng)它是非確定型圖靈機(jī)多項(xiàng)式時(shí)間可計(jì)算的。 (3)Rabin與Scott兩個(gè)人最先在IBM做的工作。 定義了非確定型計(jì)算，也就有了非確定型圖靈機(jī)。,多項(xiàng)式算法,多項(xiàng)式變換與NPC類(lèi)，上次講到什么是多項(xiàng)式變換。 我們需要什么？定義多項(xiàng)式變換，達(dá)到如下目標(biāo)：,R-S的,非確定圖靈機(jī)的時(shí)間復(fù)雜性難定義。 只關(guān)心回答Yes的實(shí)例的時(shí)間就好說(shuō)了。 NP問(wèn)題可以認(rèn)為若實(shí)例回答是， 則存在不確定多項(xiàng)式時(shí)間算法正確回答的判定問(wèn)題類(lèi)。 *在定義NP問(wèn)題時(shí)，只關(guān)心問(wèn)題的那些回答Yes的實(shí)例。 回答No的實(shí)例不關(guān)心。 NP類(lèi)：若對(duì)回答Yes的問(wèn)題實(shí)例，存在NTM程序能夠多項(xiàng)式 時(shí)間回答是，則這個(gè)問(wèn)題就屬于NP類(lèi)。 *用不著關(guān)心那些回答No的實(shí)例。為什么？能夠達(dá)到目的了。 前人就是這么定義的。,若有實(shí)例I，猜測(cè)機(jī)猜測(cè)了一個(gè)解放到讀寫(xiě)帶上，我們的程序驗(yàn)證回答是，則可以回答I是一個(gè)回答是的實(shí)例； 不需要定義的是回答否的那些實(shí)例： 若猜測(cè)機(jī)猜測(cè)了一個(gè)解放到讀寫(xiě)帶上，我們的程序驗(yàn)證回答否，不知道I是否是回答否的實(shí)例，所以干脆不定義！,希望： 若1可以多項(xiàng)式歸約到2，2存在多項(xiàng)式算法， 則1也有多項(xiàng)式算法。 前面的多項(xiàng)式歸約進(jìn)一步修改如下： 認(rèn)為與前面的定義等價(jià)。只關(guān)心那些回答yes的實(shí)例了。,1=；2= 變換f：,(1)IL1，f(I)L2， (2)1(I)=12(f(I)=1，充分必要的。 IY(1)f(I)Y(2)。不關(guān)心回答No的實(shí)例。 實(shí)際前面NTM定義中就只關(guān)心回答Yes的實(shí)例。 (3)f變換可以在p(|I|=n)時(shí)間內(nèi)計(jì)算完成。,1,2,*P問(wèn)題可以在多項(xiàng)式時(shí)間回答是或否。 *NP問(wèn)題只能在多項(xiàng)式時(shí)間回答是。 * P問(wèn)題可以在多項(xiàng)式時(shí)間判定解的存在性。 *NP問(wèn)題只能多項(xiàng)式時(shí)間驗(yàn)證解存在。 *1變換為2，當(dāng)然希望2是多項(xiàng)式時(shí)間可計(jì)算的。,引理3.1：若12，2P，則1P。 注意一點(diǎn)，當(dāng)多項(xiàng)式可解時(shí)， 否的實(shí)例也能在多項(xiàng)式時(shí)間回答。 證明：回答是的實(shí)例能夠變換，回答否的實(shí)例也能夠變換。 當(dāng)2P時(shí)，是和否都能多項(xiàng)式時(shí)間回答。 當(dāng)然1實(shí)例回答是和否也能多項(xiàng)式時(shí)間回答 下面又要回憶前面的內(nèi)容了！,I,f(I),1 2,再解釋非確定Turing機(jī)：規(guī)定 (1)猜測(cè)部件把猜測(cè)的解寫(xiě)在從-1開(kāi)始向左的存儲(chǔ)帶上。 (2)我們自己編寫(xiě)的驗(yàn)證程序直接使用帶方格x,-1中的猜測(cè)信息。 (3)實(shí)際這不是最早(Rabin,Scott)的非確定型圖靈機(jī)版本。 (4)NP問(wèn)題，多種定義版本，多項(xiàng)式時(shí)間可驗(yàn)證的， NTM多項(xiàng)式時(shí)間可求解的。,該說(shuō)明什么是NP-Complete問(wèn)題了。 期望：若有一個(gè)特殊NP問(wèn)題， 任意一個(gè)NP問(wèn)題均可多項(xiàng)式時(shí)間歸約到該問(wèn)題， 則該問(wèn)題非常特殊，稱(chēng)為NP-Complete問(wèn)題。 要求是NP類(lèi)問(wèn)題。 若NP-Complete問(wèn)題可以多項(xiàng)式時(shí)間解決， 則其他所有NP問(wèn)題都可以在多項(xiàng)式時(shí)間解決。 所有NP問(wèn)題都能多項(xiàng)式時(shí)間可解，這件事其實(shí)很大的重任。 幾乎不可能的，所以NP-C問(wèn)題多項(xiàng)式時(shí)間可解， 也是不可能的。,解釋?zhuān)喝绻鸑P-C行， 什么鳥(niǎo)都行！,每個(gè)NP問(wèn)題都存在多項(xiàng)式時(shí)間解答算法嗎？,(1)首先要搞清楚， 現(xiàn)在我們研究的問(wèn)題是多項(xiàng)式時(shí)間可驗(yàn)證的問(wèn)題類(lèi)， 最后只需要回答是和否即可以。 (2)有很多問(wèn)題不是多項(xiàng)式時(shí)間可驗(yàn)證的，那個(gè)留到以后再說(shuō)。 因此也不是NPC的。這就是為什么只研究判定問(wèn)題了。 (3)判定問(wèn)題正面絕大多數(shù)都是多項(xiàng)式時(shí)間可驗(yàn)證的。,多項(xiàng)式變換的符號(hào)： 引理3.2：12，23，則13 定義3.10：12，21，則稱(chēng)1和2多項(xiàng)式等價(jià)。,定義3.11：NP，1NP，1，則稱(chēng)是NP-Complete的。 NP-完全的。其他人有很多叫法。 簡(jiǎn)稱(chēng)NPC問(wèn)題。若是NPC問(wèn)題， 定義的含義： 有多項(xiàng)式時(shí)間算法，則任意NP問(wèn)題都有多項(xiàng)式時(shí)間求解算法。,定理3.12：若有， NPC，則下述(1)(2)等價(jià)。 (1)PNP；(2) P，即：PNP P,定理：若1NPC，2NP，12，則2NPC 就是說(shuō)1與2是多項(xiàng)式等價(jià)的。有一個(gè)是多項(xiàng)式的， 則另一個(gè)也是多項(xiàng)式的。 這是最重要的一個(gè)定理。只要有了一個(gè)NPC， 其他問(wèn)題也可以證明NPC了。 下面的問(wèn)題是尋找第一個(gè)NPC問(wèn)題。,1970年Cook證明Sat問(wèn)題是NP-完全問(wèn)題。 即Cook定理。 SAT的例子：是否存在U=u1,u2,u3,u4,u5的真值指派，使 Y = ( )( )( )( )=T,3.5Cook定理 任意一個(gè)NP問(wèn)題都有一個(gè)多項(xiàng)式時(shí)間驗(yàn)證程序。 多項(xiàng)式時(shí)間驗(yàn)證結(jié)果回答Yes。 一個(gè)問(wèn)題要形式化描述，怎么描述？ 1970年Cook證明Sat問(wèn)題是NP-完全問(wèn)題。即Cook定理。,實(shí)例：U=u1,u2,u3,u4,u5,C=C1,C2,C3,C4 詢(xún)問(wèn)：If there is an assignment of U such that all clauses in C are satisefied？,定理3.4：SAT NPC。 證明：(要說(shuō)明如果SAT有多項(xiàng)式時(shí)間算法，則所有NP問(wèn)題 都有多項(xiàng)式算法) (1)SATNP，首先要驗(yàn)證這個(gè)。 不驗(yàn)證不能說(shuō)明是NPC。 不屬于NP是否屬于NPC? 不屬于。 (2)將任意一個(gè)NP問(wèn)題多項(xiàng)式歸約到Sat。 任意NP問(wèn)題的實(shí)例：x1, x2, , xn 這與Sat問(wèn)題沒(méi)法建立起聯(lián)系來(lái)，要建立聯(lián)系，還靠NTM。 *每個(gè)NP問(wèn)題都對(duì)應(yīng)一個(gè)NTM的多項(xiàng)式時(shí)間驗(yàn)證程序。 該驗(yàn)證程序最后回答Yes或No。 只對(duì)yes的實(shí)例多項(xiàng)式時(shí)間回答是。 但是我們只關(guān)心回答Yes的NP問(wèn)題實(shí)例。 任意一個(gè)NP問(wèn)題的回答yes的實(shí)例放在NTM存儲(chǔ)帶上， NTM程序多項(xiàng)式時(shí)間步驗(yàn)證給出正確回答。,若NP,1,1,則是NP-Complete.,設(shè)NTM描述為：描述問(wèn)題需要的符號(hào)集 =s1,s2,sm=s1, s2, , sm, si=si Q=q0,q1=qy,q2=qn,q3,qr (qi,si)=(qi,si,i)，變化規(guī)則早已確定了，就是程序。 P(n)：M接受輸入I，|I| = n，I是回答是的實(shí)例， I：sk1, sk2, , skn 按照計(jì)算，對(duì)于猜測(cè)的解，經(jīng)過(guò)不超過(guò)P(n)步計(jì)算， 到達(dá)停機(jī)態(tài)qy，P(n)是n的多項(xiàng)式函數(shù)。 最多有(r+1)(m+1)條規(guī)則。,問(wèn)題實(shí)例,每個(gè)實(shí)例都存放在讀寫(xiě)帶上了，要把這個(gè)實(shí)例變成SAT的實(shí)例。 實(shí)例為：sk1, sk2, , skn。 怎樣把這個(gè)實(shí)例變成SAT實(shí)例？ 這個(gè)實(shí)例回答Yes變成的SAT實(shí)例也回答Yes。 要借助別的東西，借助驗(yàn)證程序。 可以形式化地描述驗(yàn)證程序， (qi, si)(qi ,si ,i) 下面是所有的規(guī)則：(r+1)(m+1)條,一個(gè)實(shí)例回答是，就意味著存在一個(gè)NTM程序M，執(zhí)行M可多項(xiàng)式時(shí)間停機(jī)在qy,NTM執(zhí)行程序的每一步狀態(tài)都可以用SAT布爾變量表示。 開(kāi)始?xì)w約：變量描述求解過(guò)程，項(xiàng)約束求解中程序遵循的規(guī)則。 1定義三種變量描述NTM的求解狀態(tài)， (1)Qi,k:描述狀態(tài)，0iP(n)，0kr， 在時(shí)刻i，M處于狀態(tài)qk，(r+1)(P(n)+1)個(gè)這樣的變量。 (2)Hi,j：描述讀寫(xiě)頭位置，0iP(n)，-P(n)jP(n)， 在時(shí)刻i，M讀寫(xiě)頭正掃描帶方格j。(2P(n)+1)(P(n)+1)個(gè)變量。 (3)Si,j,l：描述帶方格內(nèi)容，0iP(n)，-P(n)jP(n)，0lm， 在i時(shí)刻,帶方格j中存儲(chǔ)的符號(hào)為sl，(m+1)(2P(n)+1)(P(n)+1)。,其實(shí)，是想用Sat的語(yǔ)句來(lái)描述任意一個(gè)NP問(wèn)題是怎樣驗(yàn)證的。也就是描述NP問(wèn)題是怎樣回答是的。怎樣回答是，就把問(wèn)題自身特點(diǎn)描述出來(lái)了，就是用NTM程序表達(dá)了問(wèn)題本身的個(gè)性。,解釋?zhuān)簭?到P(n)每一個(gè)時(shí)刻的Turing機(jī)狀態(tài)， 讀寫(xiě)頭位置，讀寫(xiě)帶上的符號(hào)。都已經(jīng)描述出來(lái)了。 2NTM程序接受判定問(wèn)題的實(shí)例I，M運(yùn)行中應(yīng)遵循下述規(guī)則。,G1：在時(shí)刻i，M確切處在一個(gè)狀態(tài) (1)Qi,0,Qi,1,Qi,r，0iP(n) (2) ，0iP(n)，0jjr,(1)有P(n)+1個(gè)， (2)有(P(n)+1)P(n)/2個(gè),P(n)+1個(gè),(2)不能同時(shí)有兩個(gè)符號(hào)： ， ， 0iP(n)，-P(n)jP(n)，0 kkm,G3的構(gòu)成：在i時(shí)刻，每個(gè)帶方格中含有一個(gè)固定的符號(hào) (1)Si,j,0,Si,j,1,Si,j,m，0iP(n)，-P(n)jP(n) i時(shí)刻，j號(hào)帶方格中的內(nèi)容可能是b,s1,sm,G4的構(gòu)成：確定初始狀態(tài)： (1)Q0,0：0時(shí)刻狀態(tài)為q0 (2)H0,0：0時(shí)刻讀寫(xiě)頭位于0號(hào)帶方格 S0,0,0，S0,1,k1，S0,n,kn S0,n+1,0，S0,n+2,0，S0,P(n),0 0時(shí)刻帶方格中的內(nèi)容分別為：s0,sk1,skn。 其他帶方格中是什么內(nèi)容？-1，-P(n) 有個(gè)秘密：猜測(cè)信息放在-1，-P(n),G5：在P(n)時(shí)刻，NTM處于接受狀態(tài)。因?yàn)檫@是回答yes的實(shí)例 QP(n),1，時(shí)刻P(n)的NTM狀態(tài)為qy=q1。接受狀態(tài)。,G6:描述NTM必須按照程序的規(guī)則運(yùn)行。 G6=G61G62，兩個(gè)子項(xiàng) G61：保證在時(shí)刻i，若讀寫(xiě)頭不掃描帶方格j， 則在時(shí)刻i+1，j帶方格的內(nèi)容與i時(shí)刻j帶方格的內(nèi)容相同。 不能隨便改變。 ，Hi,j,Si+1,j,l，0iP(n)，-P(n)jP(n)，0lm,若 Si,j,l=1,Hi,j=0,則Si+1,j,l=1 G61的個(gè)數(shù)：(P(n)+1)(2P(n)+1)(m+1),G62：當(dāng)NTM程序從一個(gè)狀態(tài)轉(zhuǎn)到另一個(gè)狀態(tài)時(shí)， 狀態(tài)變化，讀寫(xiě)頭移動(dòng)，符號(hào)改變遵從函數(shù)。 (qk,sl)=( ) 必須按照這樣的規(guī)則執(zhí)行，改變狀態(tài)。 狀態(tài)轉(zhuǎn)換函數(shù)個(gè)數(shù)：(r+1)(m+1),),若Hi,j=1, Qi,k=1, Si,j,l=1, 則Hi+1,j+=1,i時(shí)刻的狀態(tài)為qk，讀寫(xiě)頭位置為j，j方格中的符號(hào)為sl 則讀寫(xiě)頭移動(dòng)為。 0iP(n)，-P(n)jP(n)，0kr，0lm 所以這樣的clause個(gè)數(shù)是： (P(n)+1)(2P(n)+1)(r+1)(m+1),(2)若Hi,j=1, Qi,k=1, Si,j,l=1, 則Qi+1,k=1 0iP(n)，-P(n) j P(n)，0kr，0 l m。,所以(2)的clause個(gè)數(shù)是：(P(n)+1)(2P(n)+1)(r+1)(m+1),(3)Hi,j=1, Qi,k=1, Si,j,l=1, 則Si+1,j,l=1 0iP(n)，-P(n)jP(n)，0kr，0Lm,(3)的個(gè)數(shù)也不超過(guò)：(P(n)+1)(2P(n)+1)(r+1)(m+1),上面是規(guī)約，首先說(shuō)明這個(gè)規(guī)約是多項(xiàng)式規(guī)約， G1, G2, G3, G4, G5, G6都是多項(xiàng)式個(gè)clause，因此是多項(xiàng)式規(guī)約。 G1: P(n)+1+(P(n)+1)P(n)/2個(gè) G2: 2P(n)+1+(P(n)+1)(2P(n)+1)(2P(n)/2個(gè) G3: (P(n)+1)(2P(n)+1)+(P(n)+1)(2P(n)+1)(m+1)m/2個(gè) G4: P(n)+3 G5: 1 G61: (P(n)+1)(2P(n)+1)(m+1) G62: (P(n)+1)(2P(n)+1)(r+1)(m+1) +(P(n)+1)(2P(n)+1)(r+1)(m+1) +(P(n)+1)(2P(n)+1)(r+1)(m+1),若的實(shí)例I回答yes，則NTM程序最后停機(jī)在qy， 則必存在一個(gè)sat變量的真值指派使每個(gè)項(xiàng)均滿足。 若sat實(shí)例存在真值指派使每個(gè)項(xiàng)均滿足， 則最后NTM會(huì)停機(jī)在yes態(tài)，相應(yīng)問(wèn)題的實(shí)例回答yes。 這就證明了第一個(gè)NP-complete問(wèn)題。,再說(shuō)明： *為什么SAT能多項(xiàng)式時(shí)間可解，則NTM就不用猜測(cè)解了。 *S0,-1,s1，S0,-1,s2，S0,-1,sm， * S0,-2,s1，S0,-2,s2，S0,-2,sm * * S0,-P(n),s1，S0,-P(n),s2