計(jì)算理論-計(jì)算復(fù)雜性-2016

教材:[1][王]王曉東,計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版),電子工業(yè).[2][S]唐常杰等譯,Sipser著,計(jì)算理論導(dǎo)引,機(jī)械工業(yè).參考資料:[3][C]潘金貴等譯,Cormen等著,算法導(dǎo)論,機(jī)械工業(yè).[4][M]黃林鵬等譯,Manber著,算法引論-一種創(chuàng)造性方法,電子.[5][劉]劉汝佳等,算法藝術(shù)與信息學(xué)競賽,清華大學(xué).[6][L]Lewis等著,計(jì)算理論基礎(chǔ),清華大學(xué).計(jì)算理論與

算法分析設(shè)計(jì)劉慶暉計(jì)算理論

第三部分計(jì)算復(fù)雜性第7章時(shí)間復(fù)雜性1.時(shí)間復(fù)雜性

{0k1k|k0}的時(shí)間復(fù)雜性分析2.不同模型的運(yùn)行時(shí)間比較單帶與多帶確定與非確定3.P類與NP類4.NP完全性及NP完全問題一.時(shí)間復(fù)雜度

時(shí)間復(fù)雜度定義

{0k1k|k0}的時(shí)間復(fù)雜度分析時(shí)間復(fù)雜性

判定器M的運(yùn)行時(shí)間或時(shí)間復(fù)雜度是f:NN,f(n)是M在所有長為n的輸入上運(yùn)行的最大步數(shù).

若f(n)是M的運(yùn)行時(shí)間,則稱

M在時(shí)間f(n)內(nèi)運(yùn)行或M是f(n)時(shí)間圖靈機(jī)舉例:大O與小o記法對(duì)于函數(shù)f,g:NR+,記f(n)=O(g(n),若存在c>0使得記f(n)=o(g(n)),若分析算法討論語言A={0k1k|k0}的復(fù)雜性:M1=“對(duì)輸入串w:1)掃描帶,如果在1的右邊發(fā)現(xiàn)0,則拒絕.2)如果0和1都在帶上,就重復(fù)下一步.3)掃描帶,刪除一個(gè)0和一個(gè)1.4)如果帶上同時(shí)沒有0和1,就接受.”時(shí)間分析:(1)2n=O(n),4)n=O(n),

{

(2)2n=O(n)+

(3)2n=O(n)}(n/2)=O(n2)所以M1的運(yùn)行時(shí)間是O(n2).時(shí)間復(fù)雜性類定義:對(duì)于函數(shù)t:NN,時(shí)間復(fù)雜性類TIME(t(n))

定義為:TIME(t(n))={L|存在O(t(n))時(shí)間TM判定L}因?yàn)镸1是時(shí)間O(n2)圖靈機(jī),所以A={0k1k:k0}TIME(n2).是否存在更快的TM判定A呢?圖靈機(jī)M2M2=“對(duì)輸入串w:1)掃描帶,若1的右邊有0,則拒絕.2)若0,1都在帶上,重復(fù)以下步驟.3)檢查帶上0,1總數(shù)的奇偶性,

若是奇數(shù),就拒絕.4)再次掃描帶,

第1個(gè)0開始,隔1個(gè)0刪除1個(gè)0;

第1個(gè)1開始,隔1個(gè)1刪除1個(gè)1.5)若帶上同時(shí)沒有0和1,則接受.

否則拒絕.”O(jiān)(n)O(n)O(n)O(n)O(n)logn總時(shí)間:O(nlogn){0k1k|k0}TIME(nlogn)由圖靈機(jī)M2知道ATIME(nlogn)有沒有更快的圖靈機(jī)識(shí)別A?對(duì)于單帶確定圖靈機(jī),由定理:時(shí)間o(nlogn)的單帶圖靈機(jī)判定的語言

是正則語言.TIME(o(nlogn))正則語言類TIME(n)

正則語言類=TIME(n)=TIME(o(nlogn))非正則語言{0k1k|k0}TIME(o(nlogn))二.

不同模型的時(shí)間復(fù)雜度比較

單帶與多帶確定與非確定單帶與多帶運(yùn)行時(shí)間比較{0k1k|k0}有O(n)時(shí)間雙帶圖靈機(jī)M3=“對(duì)輸入串w:1)掃描1帶,如果在1的右邊發(fā)現(xiàn)0,則拒絕.2)將1帶的1復(fù)制到2帶上.3)每刪除一個(gè)1帶的0就刪除一個(gè)2帶的1.4)如果兩帶上同時(shí)沒有0和1,就接受.”定理:設(shè)函數(shù)t(n)n,則每個(gè)t(n)時(shí)間多帶TM

和某個(gè)O(t2(n))時(shí)間單帶TM等價(jià).{0k1k|k0}的O(n)時(shí)間雙帶圖靈機(jī)q0q1└┘qaq2└┘└┘└┘└┘NTM的運(yùn)行時(shí)間定義:對(duì)非確定型判定器N,其運(yùn)行時(shí)間f(n)是在所有長為n的輸入上,所有分支的最大步數(shù)....f(n)接受/拒絕...f(n).........TMNTM定理:設(shè)t(n)n,則每個(gè)時(shí)間t(n)NTM都有一等價(jià)的時(shí)間2O(t(n))TM.NTIME(t(n))TIME(2O(t(n)))

三.P與NP多項(xiàng)式時(shí)間運(yùn)行時(shí)間相差多項(xiàng)式可以認(rèn)為是小的相差指數(shù)可以認(rèn)為是大的.例如:n3與2n,對(duì)于n=1000.有關(guān)素性測(cè)試:Prime={p|p是素?cái)?shù)}如何編碼?一進(jìn)制,二進(jìn)制,十進(jìn)制?典型的指數(shù)時(shí)間算法來源于蠻力搜索.有時(shí)通過深入理解問題可以避免蠻搜.2001年P(guān)rime被證明存在多項(xiàng)式時(shí)間算法.P類定義:P是單帶確定TM在

多項(xiàng)式時(shí)間內(nèi)可判定的問題,即

P=kTIME(nk)P類的重要性在于:對(duì)于所有與單帶確定TM等價(jià)的模型,P不變.P大致對(duì)應(yīng)于在計(jì)算機(jī)上實(shí)際可解的問題.

研究的核心是一個(gè)問題是否屬于P類.NP類NTIME(t(n))={L|L可被O(t(n))時(shí)間NTM判定.}定義:NP是單帶非確定TM在

多項(xiàng)式時(shí)間內(nèi)可判定的問題,即

NP=kNTIME(nk)EXP=∪kTIME(2^(nk))PNPEXPPEXP一些P問題有些問題初看起來不屬于P求最大公因子:歐幾里德算法,

輾轉(zhuǎn)相除法模p指數(shù)運(yùn)算abmodp素性測(cè)試等等以增加空間復(fù)雜性來減小時(shí)間復(fù)雜性上下文無關(guān)語言有O(n3)判定器

快速驗(yàn)證HP={<G,s,t>|G是包含從s到t的

哈密頓路徑的有向圖}CLIQUE={<G,k>|G是有k團(tuán)的無向圖}目前沒有快速算法,但其成員是可以快速驗(yàn)證的.注意:HP的補(bǔ)可能不是可以快速驗(yàn)證的.快速驗(yàn)證的特點(diǎn):只需要對(duì)語言中的串能快速驗(yàn)證.驗(yàn)證需要借助額外的信息:證書,身份證.NP問題團(tuán):無向圖的完全子圖(所有節(jié)點(diǎn)都有邊相連).CLIQUE={<G,k>|G是有k團(tuán)的無向圖}定理:CLIQUENP.N=“對(duì)于輸入<G,k>,這里G是一個(gè)圖:1)非確定地選擇G中k個(gè)節(jié)點(diǎn)的子集c.2)檢查G是否包含連接c中節(jié)點(diǎn)的所有邊.3)若是,則接受;否則,拒絕.”哈密頓路徑問題HPNPHP={<G,s,t>|G是包含從s到t的

哈密頓路徑的有向圖}P時(shí)間內(nèi)判定HP的NTM:N1=“對(duì)于輸入<G,s,t>:1)非確定地選G的所有節(jié)點(diǎn)的排列p1,…pm.2)若s=p1,t=pm,且對(duì)每個(gè)i,(pi,pi+1)是G的邊,

則接受;否則拒絕.”P與NPP=成員資格可以快速判定的語言類.NP=成員資格可以快速驗(yàn)證的語言類.顯然有PNP但是否有P=NP?看起來難以想象,但是現(xiàn)在沒有發(fā)現(xiàn)反例.PNPP=NP當(dāng)代數(shù)學(xué)與理論計(jì)算機(jī)共同的難題.NP完全性的定義

SAT是NP完全問題一些NP完全問題NP完全性Cook和Levin于70’s證明NP中某些問題的復(fù)雜性與

整個(gè)NP類的復(fù)雜性相關(guān)聯(lián),即:若這些問題中的任一個(gè)找到P時(shí)間算法,則P=NP.這些問題稱為NP完全問題.理論意義:兩方面1)研究P與NP關(guān)系可以只關(guān)注于一個(gè)問題的算法.2)可由此說明一個(gè)問題目前還沒有快速算法.合取范式

布爾變量:取值為1和0(T,F)的變量.

布爾運(yùn)算:AND(),OR(),NOT().布爾公式.

例:1=((x)y)(x(z)),2=(x)x

稱可滿足,若存在布爾變量的0,1賦值使得=1.不可滿足永真合取范式:正負(fù)文字(變量,變量的非)子句(文字的或)

((x1)x2(x3))(x2(x3)x4x5)((x4)x5)

合取范式cnf(conjunctivenormalform)3cnf:每個(gè)子句文字?jǐn)?shù)不大于3,

2cnf:每個(gè)子句文字?jǐn)?shù)不大于2可滿足問題SAT

可滿足性問題:SAT={<>|是可滿足的布爾公式

}

二元可滿足性問題:2SAT={<>|是可滿足的2cnf}

三元可滿足性問題:3SAT={<>|是可滿足的3cnf}二元可滿足問題2SATP1.當(dāng)2cnf中有子句是單文字x,則反復(fù)執(zhí)行清洗

1.1由x賦值,1.2刪去含x的子句,1.3刪去含x的文字若清洗過程出現(xiàn)相反單文子子句,則清洗失敗并結(jié)束(x1x2)(x3x2)(x1)(x1x2)(x3x4)(x3x5)(x4x5)(x3x4)(x3x2)(x2)(x3x4)(x3x5)(x4x5)(x3x4)(x3x4)(x3x5)(x4x5)(x3x4)2.若無單文字子句,則任選變量賦真/假值各清洗一次若兩次都清洗失敗,則回答不可滿足.x3:(x5)(x4x5)(x4)(x4)(x4)失敗

x3:(x4)(x4x5)(x5)成功3.若成功清洗后有子句剩下,則繼續(xù)2.否則,回答可滿足.注:見[S]習(xí)題7.23,作者給出的答案與清洗算法等價(jià)多項(xiàng)式時(shí)間映射歸約與C-L定理Cook-Levin定理:SATPP=NP.

定義:多項(xiàng)式時(shí)間可計(jì)算函數(shù)f:**.

定義:稱A可多項(xiàng)式時(shí)間映射歸約到B(APB),

若存在多項(xiàng)式時(shí)間可計(jì)算函數(shù)f:**,

w*,wAf(w)B.

函數(shù)f稱為A到B的多項(xiàng)式時(shí)間歸約.

通俗地說:f將A的實(shí)例編碼轉(zhuǎn)換為B的實(shí)例編碼.Cook-Levin定理:對(duì)任意ANP都有APSAT.

定理1:若APB,且BP,則AP.

注:定理1說明,若SATP,則NP=P.多項(xiàng)式時(shí)間映射歸約的作用

輸入wff(w)My/nw*,wAf(w)B.

定理1:若APB,且BP,則AP.

證明:設(shè)f:**是A到B的P時(shí)間歸約,B有P時(shí)間判定器M,則

N=“輸入w,計(jì)算M(f(w)),輸出M的運(yùn)行結(jié)果”在多項(xiàng)式時(shí)間內(nèi)判定A.利用f和B的判定器

構(gòu)造A的判定器定理:3SATPCLIQUE3SAT={<>|是可滿足的3cnf公式}CLIQUE={<G,k>|G是有k團(tuán)的無向圖}.證明:設(shè)=(a1b1c1)…(akbkck),有k個(gè)子句.f()=<G,k>,G有k組節(jié)點(diǎn),每組3個(gè);

同組節(jié)點(diǎn)無邊相連,相反標(biāo)記無邊相連.f((x1x1x2)(x1x2x2)(x1x2x2))=<G,3>x1x1x2x1x2x2x1x2x2需證:3SAT

(G,k)CLIQUE,3SATf()CLIQUE

<>(<(x1x1x2)(x1x2x2)(x1x2x2)>)

3SAT變量賦值(x1=0,x2=1)使得=1k團(tuán)(每組挑一個(gè)真頂點(diǎn)得到k團(tuán),非同組非相反)f()(<G,3>)CLIQUE.x1x1x2x1x2x2x1x2x2NP完全性

定義:語言B稱為NP完全的(NPC),若它滿足:1)BNP;2)ANP,都有APB.

定理1:若APB,且BP,則AP.

定理2:若B是NPC,且BP,則P=NP.

定理3:若B是NPC,BPC,且CNP,則C是NPC.

證明:ANP,(APB)+(BPC)APCCook-Levin定理:SAT是NP完全問題.

推論:CLIQUE是NPC.

輸入wff(w)My/nw*,wAf(w)B.利用f和B的判定器

構(gòu)造A的判定器Cook-Levin定理的證明步驟

定義:語言B稱為NP完全的(NPC),若它滿足:1)BNP;2)ANP,都有APB.Cook-Levin定理:SAT是NP完全問題.證明步驟:1.SATNP(?),2.ANP,AP

SAT(?)N=“對(duì)于輸入<>,是一個(gè)布爾公式:

1)非確定地選擇所有變量的賦值T.

2)檢查在賦值T下是否=1

3)若是,則接受;否則,拒絕.”SAT是NP完全問題

要證明:1)SATNP.2)ANP,都有AP

SAT.

思想:將字符串對(duì)應(yīng)到布爾公式利用接受的形式定義.

過程:任取ANP,設(shè)N是A的nk時(shí)間NTM.w(|w|=n),N接受w

N有長度小于nk的接受格局序列能填好N在w上的畫面(一個(gè)nknk表格)f(w)可滿足

結(jié)論:SAT是NP完全的N接受w能填好N在w上的畫面#q0w0w1…wn#####nknk起始格局第2個(gè)格局第nk個(gè)格局窗口能填好畫面:第一行是起始格局上一行能產(chǎn)生(或等于)下一行

畫面中有接受狀態(tài)構(gòu)造布爾公式f(w)

能填好畫面f(w)可滿足

f(w)=<>,=cellstartmoveaccept.

對(duì)于任意賦值:1.cell=1每格有且只有一個(gè)符號(hào);2.start=1第一行是起始格局;3.accept=1表格中有接受狀態(tài);4.move=1每行由上一行格局產(chǎn)生.

w,wA<>SAT即AmSAT

若|<>|是|w|的多項(xiàng)式,則有APSAT構(gòu)造cell

長O(n2k)

cell=1每格有且只有一個(gè)符號(hào);的變量:xi,j,s,i,j=1,…,nk,sQ{#}

xi,j,s:第i行第j列是否填了符號(hào)s構(gòu)造start

長O(nk)

start=1第一行是起始格局;構(gòu)造accept

長O(n2k)

accept=1表格中有接受狀態(tài)構(gòu)造move=cellstartmoveaccept.move確定表的每行是上一行的合法結(jié)果.只需判斷每個(gè)23窗口是否“合法”.合法窗口設(shè)(q1,b)={(q2,c,L),(q2,e,R)},a,d,s,t是任意符號(hào),則aq1bq2acaq1baeq2daq1daeasbasbstastq2bsacsaabtastaq1baaq1aq1bq1aq1合法窗口非法窗口長

O(n2k)APSAT,SAT是NPCf(w)=<>wA<>SAT,

|<>|=O(n2k)=cellstartmoveaccept.推論:3SAT是NP完全的只需將前面的改造為3cnf公式.=cellstartmoveaccept.任取變量賦值

a1a2…ak=1當(dāng)且僅當(dāng)存在新變量z的賦值使得(a1a2…ak-2z

)(z

ak-1ak

)=1改造后公式長度最多是原來的3倍move的改造分配律(ab)c=(ac)(bc)

(ab)(cd)(ef)=(ace)(acf)設(shè)合法窗口有M個(gè),則move原長度是6Mn2k,改造為cnf范式后,move長度是6Mn2k.改造為3cnf后,長度增加常數(shù)倍.所以3SAT是NP完全的.恰當(dāng)覆蓋問題(ExactCover,EC)

有限集U,論域,全集子集簇F={S1,S2,…,Sm}

是否有F的兩兩不交子簇,其并為U

例:U={1,…,6},F={{1,3},{2,3,6},{1,5},{2,3,4},{5,6},{2,4}}

定理:ECNP.

證明:非確定選擇子集簇,驗(yàn)證.

定理:3SATPEC.定理:3SATPEC.EC={<(U,F)>|U的子集簇F有不交子簇并為U}

對(duì)于3cnf公式,構(gòu)造f(<>)=<(U,F)>

設(shè)有變量x1,…,xn,子句C1,…,Cs,Cj有文字ajk,1k3U={x1,…,xn}{C1,…,Cs}{pjk|1js,1k3}F由下面的集合組成變量子集Ti,1={xi}{pjk|ajk=xi}xi的負(fù)文字

Ti,0={xi}{pjk|ajk=xi}xi的正文字子句子集{Cj,pjk},文字子集{pjk}可滿足(U,F)有恰當(dāng)覆蓋原則:子句子集對(duì)應(yīng)真文字,變量子集對(duì)應(yīng)假文字,文字子集補(bǔ)齊到(U,F)歸約舉例EC={<(U,F)>|U的子集簇F有不交子簇并為U}設(shè)C1=(x1x2),C2=(x1x2x3),C3=(x2),C4=(x2x3),則U={x1,x2,x3}{C1,C2,C3,C4}{p11,p12,p21,p22,p23,p31,p41,p42}F由下面的集合組成變量子集T1,1={x1,p21},T1,0={x1,p11},T2,1={x2,p12,p41},T2,0={x2,p22,p31},T3,1={x3,p42},T3,0={x3,p23},

子句子集{C1,p11},{C1,p12},…,{C4,p41},{C4,p42},

文字子集{p11},{p12},…,{p41},{p42},

原則:子句子集對(duì)應(yīng)真文字,變量子集對(duì)應(yīng)假文字,文字子集補(bǔ)齊哈密頓路徑(HP)是NPC(3SATPHP)HP={<G,s,t>|G是有向圖,有從s到t的哈密頓路徑}任取3cnf公式=(a1b1d1)…(akbkdk),不妨設(shè)有k個(gè)子句c1,…,

ck,n個(gè)變量x1,…,xn,構(gòu)造f()=<G,s,t>使得可滿足G有從s到t的HP一般從3cnf公式構(gòu)造圖有

變量構(gòu)件,子句構(gòu)件,聯(lián)接構(gòu)件變量構(gòu)件和子句構(gòu)件變量xi表示為一個(gè)鉆石結(jié)構(gòu)xicj子句cj表示為一個(gè)節(jié)點(diǎn)圖G的總體結(jié)構(gòu)對(duì)應(yīng)n個(gè)變量x1,…,xn,k個(gè)子句c1,…,ck,起點(diǎn)s,終點(diǎn)t

st鉆石構(gòu)件中的水平節(jié)點(diǎn)分隔節(jié)點(diǎn)xi分隔節(jié)點(diǎn)c1c2水平行除兩端的兩個(gè)節(jié)點(diǎn)外有3k+1個(gè)節(jié)點(diǎn)每個(gè)子句對(duì)應(yīng)一對(duì)節(jié)點(diǎn)(共2k個(gè))用分隔節(jié)點(diǎn)隔開(k+1個(gè))變量與子句構(gòu)件的連接xi分隔節(jié)點(diǎn)cj當(dāng)子句cj含有文字xi時(shí)添加的邊當(dāng)子句cj含有文字xi時(shí)添加的邊cjxi分隔節(jié)點(diǎn)cjcj可滿足G有從s到t的哈密頓路徑設(shè)計(jì)思路:變量賦值1對(duì)應(yīng)左-右式通過鉆石,反之右左式

cj可選一真文字處進(jìn)出一次正規(guī)路徑xi分隔節(jié)點(diǎn)cj當(dāng)子句cj含有文字xi時(shí)添加的邊當(dāng)子句cj含有文字xi時(shí)添加的邊cjxi分隔節(jié)點(diǎn)cjcjG有從s到t的哈密頓路徑可滿足若每個(gè)鉆石都是左右式或右左式通過,則稱為正規(guī)路徑若s到t的哈密頓路徑是正規(guī)路徑,則公式可滿足從s到t哈密頓路徑只能是正規(guī)路徑若非正規(guī)路徑,如圖,則a2或a3是分隔節(jié)點(diǎn)若a