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