算法分析與設(shè)計(jì)ss lecture7

Turing機(jī)的定義雙向無限帶的Turing基本模M=<,,qTuring機(jī)的定義雙向無限帶的Turing基本模M=<,,q0B,F其中QB有窮狀態(tài)有窮帶字符集輸入字符集空白字符,q0初始狀態(tài)qY,FF終結(jié)狀態(tài)集Q×狀態(tài)轉(zhuǎn)移函:帶B讀寫…B有限狀態(tài)控制2瞬時(shí)描述-格局(ID)1q瞬時(shí)描述-格局(ID)1q2表示此刻Turing機(jī)的FSC處于狀態(tài)q讀寫頭指在串2的第一個(gè)字符.例如TuringM的某時(shí)刻的狀態(tài)轉(zhuǎn)移函數(shù)(q,xi)=帶上的字x1x2xixn讀寫頭指向xi則它的瞬間描述是x1x2...xi-1qxi...xnx1x2...xi-2pxi-1Yxi+1...表示由左邊的ID一步達(dá)到右邊的表示由左邊的ID經(jīng)有限步達(dá)到右邊的3實(shí)L0n1n實(shí)L0n1n|n1設(shè)計(jì)接LTuring機(jī)如下M=,,,q0,Q={q0,q1,q2,q3,qY,qN={0,={0,1,X,Y,BF={qY初始將字符串放1n方格中,FSC處在狀態(tài)q0,讀寫指向方1.將第一個(gè)0改寫X,然后帶頭向右掃描.遇到一個(gè)1將1改為Y然后帶頭向左掃描遇到第一X改為向右掃描這時(shí)進(jìn)入下一個(gè)巡回.每個(gè)巡回01改為Y直到接受或拒斥停機(jī)4實(shí)例（續(xù)轉(zhuǎn)移函數(shù)如例如輸機(jī)動(dòng)作如下q00011 Xq10110Y1實(shí)例（續(xù)轉(zhuǎn)移函數(shù)如例如輸機(jī)動(dòng)作如下q00011 Xq10110Y11Y1 Y112YYXXq0YYXXYYq3501XYBTuring機(jī)接受語言被Turing機(jī)接受語言被M接受的語言記作L(M)，是*上的字的集合當(dāng)這些字左端對(duì)齊1放在帶上M處于q0M的帶頭指向1時(shí)經(jīng)過有限步M將停機(jī)在接受qY即L(M)={|*,1,2*(q0*1qY2)}如果字不是L(M)中的字, M可以不停機(jī)或停機(jī)在拒斥狀態(tài)Turing機(jī)可以推廣k條帶Turing確定型Turing機(jī)可以推廣到非確定Turing6基本Turing機(jī)的變種單向無限帶Turing帶方格從1開始基本Turing機(jī)的變種單向無限帶Turing帶方格從1開始向右無限長(zhǎng)其它與基Turing機(jī)相同多帶Turingk條雙向帶k個(gè)讀寫頭k為大1的常數(shù).初始將輸入寫在第一條帶的1n內(nèi).其它帶為空.每個(gè)讀寫頭掃描一條帶,可以改寫被掃描方格的字符,讀寫頭然后向左或向右移動(dòng)一個(gè)方格.讀寫頭FSC的狀態(tài)及k條帶所掃描的k個(gè)字符來決定7實(shí)例例LwcwR實(shí)例例LwcwR|w為0-1字符串設(shè)計(jì)L的TuringM2M1的時(shí)間復(fù)雜度為O(nM2的空間復(fù)雜度為O(logn).當(dāng)發(fā)c時(shí)第M1有2條帶,c左邊的w復(fù)制到第2條帶上2條帶的讀寫頭向左,輸入帶的讀寫頭向右.比較兩個(gè)帶頭的符號(hào),如果符號(hào)一樣,字符個(gè)數(shù)一樣,M1x.M1至多作n+1個(gè)動(dòng)作時(shí)間復(fù)雜度n+1.空間復(fù)雜(n-1)/2+1.M2有2條帶第2條帶作為二進(jìn)制的計(jì)數(shù)器首先檢查輸入是否只有1cc左邊和右邊的符號(hào)是否一樣多然后逐個(gè)比較c左邊和右邊的字符,用上述計(jì)數(shù)器找到對(duì)應(yīng)的字符.如果所有的字符都一樣M2接受停機(jī)空間復(fù)雜度為二進(jìn)制的計(jì)數(shù)器的占用空間,O(logn).時(shí)間復(fù)雜O(n2).8計(jì)算復(fù)計(jì)算復(fù)雜性理論空間和時(shí)間復(fù)雜度的形式定義確定型Turing計(jì)算復(fù)雜度的有關(guān)結(jié)果帶壓縮線性加速帶數(shù)目的減9確定型Turing空間復(fù)雜度的確定型Turing空間復(fù)雜度的形式定義&$離線的Turing1條具有端記號(hào)的只讀輸入帶k半無限存儲(chǔ)帶.如果對(duì)每個(gè)長(zhǎng)為n的輸入串,M在任一存儲(chǔ)帶上都至多S(n)那么M在最壞情況下的空間復(fù)雜度為S(n).確定型Turing機(jī)時(shí)復(fù)雜度的形式確定型Turing機(jī)時(shí)復(fù)雜度的形式定義k條雙向帶Turing一條帶包含輸入如果對(duì)于每個(gè)長(zhǎng)為n的輸入串M在停機(jī)前至多做個(gè)動(dòng)作那么稱M在最壞情況下的時(shí)間復(fù)雜度為兩條假設(shè)：空間復(fù)雜性至少需要時(shí)間復(fù)雜性至少需要讀入輸入的時(shí)因此這里作如下規(guī)定對(duì)一切nS(n)1lognmax{1,logn}的縮寫對(duì)一切nT(n)n+1,T(n)max{n+1,T(n)}的縮寫有關(guān)計(jì)算復(fù)雜度的結(jié)果帶M2模擬M1的復(fù)雜類帶壓有關(guān)計(jì)算復(fù)雜度的結(jié)果帶M2模擬M1的復(fù)雜類帶壓cS(n),0<cT(n)liminfT(n) n 時(shí)間加cT(n),帶數(shù)目減少空間不變帶數(shù)目減少時(shí)間增加7.1P類與NP易解的問題與難解的問題排序O(nlog7.1P類與NP易解的問題與難解的問題排序O(nlogn)Dijkstra算法O(n2)，最大團(tuán)回溯法用一臺(tái)每秒10次的超大型計(jì)算機(jī)，上述算法的時(shí)間105log21051.7106，t=1.710-310萬個(gè)數(shù)據(jù)排序1萬個(gè)頂點(diǎn)的圖的單源最短路徑(104)2=108,t=0.1100個(gè)頂點(diǎn)的圖的最大團(tuán),t=1.81032/109=1.81021秒=5.71015年,即5千7百萬億年1分鐘能解多大的問題.161010次運(yùn)算可給2109=20億個(gè)數(shù)據(jù)排序用Dijkstra算法可解2.4105個(gè)頂點(diǎn)的圖的單源最短路徑問題回溯法1天只能解41個(gè)頂點(diǎn)的圖的最大團(tuán)問題算法的時(shí)間復(fù)雜度f算法的時(shí)間復(fù)雜度fg是多項(xiàng)式相關(guān)的如果存在多pq使得對(duì)任意nN,f(n)p(q(n))g(n)q(f(n)).例如nlognn2,n2+2n+5n10都是多項(xiàng)式相關(guān)的,lognn,n52n不是多項(xiàng)式相關(guān)的.問題的實(shí)例I的規(guī)模:I的二進(jìn)制編碼的長(zhǎng)度記作定義7.1 如果存在函數(shù)f:NN使得對(duì)任意的規(guī)模為n的實(shí)例I,算法A對(duì)I的運(yùn)算在f(n)步內(nèi)停止,則稱算法A的時(shí)復(fù)雜度多項(xiàng)式時(shí)間算法:以多項(xiàng)式為時(shí)間復(fù)雜度易解的問題:有多項(xiàng)式時(shí)間算法難解的問題不存在多項(xiàng)式時(shí)間算法幾點(diǎn)說1當(dāng)采用合理的編幾點(diǎn)說1當(dāng)采用合理的編碼時(shí)輸入的規(guī)模都是多項(xiàng)式相關(guān)的.“合理的”是指在編碼中不故意使用許多冗余的字符例如設(shè)實(shí)I是一個(gè)無向簡(jiǎn)GV,EV={a,b,c,d},E={(a,b),(a,d),(b,c),(b,d),(c,d)用鄰接矩陣表示e1=0101/1011/0101/1110用關(guān)聯(lián)矩陣表示,編碼e2=11000/10110/00101/01011/,長(zhǎng)G有n個(gè)頂點(diǎn)m條邊用鄰接矩陣時(shí)|I|=n(n+1),用關(guān)聯(lián)矩陣時(shí)|I兩者多項(xiàng)式相關(guān)自然數(shù)應(yīng)采用 (k2)進(jìn)制編碼不能采用一進(jìn)制編碼n的二進(jìn)制編碼有l(wèi)og2(n+1)位一進(jìn)制編碼有n位兩者不是多項(xiàng)式相關(guān)的.幾點(diǎn)說明時(shí)間復(fù)雜度常表成幾點(diǎn)說明時(shí)間復(fù)雜度常表成計(jì)算對(duì)象的某些自然參數(shù)的函數(shù)，如圖的頂點(diǎn)數(shù)或邊數(shù)的函數(shù).實(shí)例的二進(jìn)制編碼的長(zhǎng)度與這自然參數(shù)通常是多項(xiàng)式相關(guān)的運(yùn)行時(shí)間通常是計(jì)算執(zhí)行的操作指令數(shù)，執(zhí)行的指令數(shù)與實(shí)際運(yùn)行時(shí)間是多項(xiàng)式相關(guān)的要求每一條指令的執(zhí)行時(shí)間是固定的常數(shù)規(guī)定一個(gè)基本操作指令集，可由位邏輯運(yùn)算與、或、非組成，任何可用這個(gè)基本操作指令集中常數(shù)條指令實(shí)現(xiàn)的操作都是合理的指令，由有限種合理的指令構(gòu)成的操作指令集是合理的操作指令集.在上述約定下作指令集無關(guān)，算法是否是多項(xiàng)式時(shí)間的與采用的編碼和操?gòu)亩粋€(gè)問題是易解的、還是難解的也與采用的編碼和操作指令集無關(guān)易解的問題與難解的問題易解的問易解的問題與難解的問題易解的問題如排序、最小生成樹、單源最短路徑已證明的難解問題(1)不可計(jì)算的即根本不存在求解的算法如希爾伯特第十問題丟番圖方程(有一個(gè)或幾個(gè)變量的整系數(shù)方程)是否有整數(shù)解有算法但至少需要指數(shù)或更多的時(shí)間或空間，如帶運(yùn)算的正則表達(dá)式的全體性即任給字母表A上的帶冪運(yùn)問:R=A*?這個(gè)問題至少需要指數(shù)空間的正則表達(dá)式既沒有找到多項(xiàng)式時(shí)間算法、又沒能證明是難解的問題如哈密頓回路問題、貨郎問題、背包問題7.1.2判定問題判定問題:答案只有兩個(gè)是否7.1.2判定問題判定問題:答案只有兩個(gè)是否<D,Y其中D是實(shí)例集合YD是所判定問答案為Yes的實(shí)例哈密頓回路任給無向圖問G有哈密頓回路嗎貨郎(TSP):n個(gè)城市城市i與城j之間的正整數(shù)距離d(i,j),ij1ijn以及正整D問有一條每一個(gè)D市恰好經(jīng)過一次最后回到出發(fā)點(diǎn)且長(zhǎng)度不超的巡回路嗎即12n的排使得d((i),(i1))d((n),(1))Di0-1背包的判定問題與優(yōu)化問0-1背包的判定問題與優(yōu)化問0-1背包n件物品和一個(gè)背包i的重wi,價(jià)vi1in,以及背包的重量B和價(jià)值目K,其wiviB,K均為正整數(shù)問能在背包中裝入總價(jià)值不少于KB的物品嗎即存在子集T{1,2使K且搜索問題、組合優(yōu)化問題與判定問題的對(duì)應(yīng)如果搜索問題、組合優(yōu)化問題有多項(xiàng)式時(shí)間算法,則對(duì)應(yīng)的判定問題也有多項(xiàng)式時(shí)間算法;通常反之亦真組合優(yōu)化問題與判定問題*由組合優(yōu)化問題與判定問題*由3部分組成組合優(yōu)化問題(1)實(shí)例集DID*有一個(gè)有窮非空集S(I其元素稱作I的可行解sS(I),有一個(gè)正整數(shù)c(s),稱作s的值s*S(I),對(duì)所sS(I),當(dāng)*是最()化問題時(shí)c(s*)(c(s*)c(s)s*I的最優(yōu)解c(s*)I的最優(yōu)值記作*對(duì)應(yīng)的判定問題D,Y>定義如下DI,K|ID*KZ*其中Z*是非負(fù)整數(shù)集合.當(dāng)*是最小化問題時(shí)Y={(I,K)|OPT(I)K};當(dāng)*是最大化問題時(shí)Y={(IK)|OPT(I)K(nondeterministic所有多項(xiàng)式時(shí)間可解的判定(nondeterministic所有多項(xiàng)式時(shí)間可解的判定問題組成的問題類定義P類設(shè)判定問題定義=<D,Y>,如果存在兩個(gè)輸入變量p，對(duì)每一個(gè)實(shí)例ID,IY多項(xiàng)式時(shí)間算A和多項(xiàng)式t,|t|p(|I|A對(duì)輸It輸出“Yes”且僅當(dāng)存在稱 是多項(xiàng)式時(shí)間可驗(yàn)證的,A是IY時(shí),tIY的證據(jù)的多項(xiàng)式時(shí)間驗(yàn)證算法由所有多項(xiàng)式時(shí)間可驗(yàn)證的判定問題組成的問題類稱類TSP(貨郎),0-1背包HC(哈密頓回路非確定型多項(xiàng)式時(shí)間算法非確定型多項(xiàng)式時(shí)間算法非確定型多項(xiàng)式時(shí)間算(1對(duì)給定的實(shí)I首先“猜想”一t|t|p(|It是否是證IY的證(2)然后檢猜想和檢查可以在多項(xiàng)式時(shí)間內(nèi)完當(dāng)且僅當(dāng)IY時(shí)能夠正確地猜想到一個(gè)證據(jù)*注：非確定型多項(xiàng)式時(shí)間算法不是真正的算定理 t問題多項(xiàng)式時(shí)間變換與NP完全性多項(xiàng)式時(shí)多項(xiàng)式時(shí)間變換與NP完全性多項(xiàng)式時(shí)間變換如何比較兩個(gè)問題的難度定義 設(shè)判定問題1=<D1,Y1>,2=f:D1D2滿足條件如果函(1)是多項(xiàng)式時(shí)間可計(jì)算的(2)對(duì)所ID1IY1則稱f是1到2的多項(xiàng)式時(shí)間變換如果存12的多項(xiàng)式時(shí)間變換則稱可多項(xiàng)式1間變換2,記作1p例例 HC例例 HC的每一個(gè)IG=<V,E>,TSP對(duì)應(yīng)的f(I為V,任意兩個(gè)不同的城市的距離uv之間若(u,v否則d(u,v)以及D|V例任給連通的無向賦權(quán)圖最小生成樹例任給連通的無向賦權(quán)圖最小生成樹以及正整B,其中權(quán)W:EZ+,問有權(quán)不超過B的生成樹嗎最大生成樹任給連通的無向賦權(quán)圖以及正整D,其中權(quán)W:EZ+,問G有權(quán)不小于D的生成樹嗎例 最大生成樹p最小生成樹證任給最大生成樹的實(shí)例I:連通的無向賦權(quán)圖和正整數(shù)D最小生成樹的對(duì)應(yīng)f(I圖G=<V,E,W>和正整B=(n1)MD,其中 M=max{W(e)|eE W(e)=MW(e)如果存在G的生成樹T,使W(e)(n1)MW(e)(n1)MDe反之亦然e多項(xiàng)式時(shí)間可計(jì)算f變換實(shí)例262633554474145317最小生變換實(shí)例262633554474145317最小生成樹T’的實(shí)例G’W(T')32最大生成樹的實(shí)GM8，W(T)16W'(e)(n1)MWeTp的性定理7.2pp的性定理7.2p具有傳遞性.即,設(shè)1p2,2p3,則1p3.i=<Di,Yii=1,2,3,fg1223的多項(xiàng)式時(shí)間變換.對(duì)每一個(gè)ID1,令h(I)=g(f(I)).fg的時(shí)間上界分別為pq不妨pq是單調(diào)遞增的.h的步數(shù)不p(|I|輸?shù)某鲎鳛楹侠淼闹噶钜徊街荒茌敵鲩L(zhǎng)度不超過固定值字符串,|f(I)|kp(|I|于是p(|I|)+q(|f(I)|)p(|I|)+q(kp(|I得證h是多項(xiàng)式時(shí)間可計(jì)算的對(duì)每一個(gè)IY1f(I)Y2h(I)得證h3的多項(xiàng)式時(shí)間變換1p的性1p2p的性1p2,2P蘊(yùn)涵1P.定理1=<D1,Y12=<D2,Y2>,f12的多項(xiàng)式時(shí)間變換A是計(jì)f的多項(xiàng)式時(shí)間算法B2的多項(xiàng)式時(shí)間算法.如下構(gòu)造1的算C:對(duì)每一ID1,應(yīng)用A得到f(I(3)C輸出Yes當(dāng)且僅B輸出設(shè)1p2,則1是難解的蘊(yùn)2是難解的推論由例7.2及最小生成樹P,得知最大生成樹P.由例7.1HCP.反過來HC是難解的TSP也是難解的7.2.2NP完全性如果對(duì)所有NP,p7.2.2NP完全性如果對(duì)所有NP,p則稱定義7.5定理7.4推論定理7.5NP難的.推論7.3, 則是NP難的NP難的NP,NP完全的P,如果存在NP難的問題假設(shè)PNP,那么,如果是NP難的,p,如果存在NP難的問題是如果NP并且存在是NP完全的.NP完全問題p證明NP完全性的捷徑證明NP;找到一個(gè)已知的NP完全問題,并證明p.Cook-Levin定理合式公Cook-Levin定理合式公式：由變?cè)?、邏輯運(yùn)算符以及圓括號(hào)按照一定的規(guī)組成的表達(dá)式變?cè)退姆穸ǚQ作文字有限個(gè)文字的析取稱作簡(jiǎn)單析取式有限個(gè)簡(jiǎn)單析取式的合取稱作合取范式給定每一個(gè)變?cè)恼婕僦捣Q作一個(gè)賦值如果賦t使得合式公F為真,tF的成真賦值.如果F存在成真賦值,則稱F是可滿足的例如F1=(x1x2)(x1x2x3)x2是一個(gè)合取范式F1是可滿足的令t(x1)=1,t(x2)=0,t(x3)=1是F1的成真賦值F2=(x1x2x3)(x1x2x3x2x3不是可滿足的Cook-Levin定理可滿足(SAT):任給一個(gè)合取Cook-Levin定理可滿足(SAT):任給一個(gè)合取范F,F是可滿足的嗎定理(Cook-Levin定理是NP完全的證明思想：對(duì)于任意一個(gè)NP類中語言L，存在一個(gè)接受它非確定型圖靈機(jī)構(gòu)造L到SAT的多項(xiàng)式變換對(duì)于L中的任意串x，M對(duì)x的接受計(jì)算變換成一個(gè)SAT問題的肯定實(shí)定理7.7P=NP的充分必要條件是存在NP完全問題P.7.3幾個(gè)NP完全問題恰好覆最大可滿足子集7.3幾個(gè)NP完全問題恰好覆最大可滿足子集有向雙機(jī)調(diào)背獨(dú)立裝團(tuán)最大可滿足性與三元可滿足性最大可最大可滿足性與三元可滿足性最大可滿足性(MAX-任給關(guān)于變?cè)獂1,xn的簡(jiǎn)析取C1,C2,,Cm及正整K問存在x1x2,的賦值使得C1,C2,,Cm中至少有個(gè)為真嗎3元合取范式每一個(gè)簡(jiǎn)單析取式恰好有3個(gè)文字的合取范式.三元可滿足性(3SAT):任給一個(gè)3元合取范式F,問F是可滿足的嗎?子問題：設(shè)判定問題=<D,Y>,=<D,Y>,如果DD,YDY,是的特殊情況,的子問題SAT是MAX-SAT的子問題(取定理7.8MAX-SAT是NP完全3SAT是SAT的子問題定理3SAT是NP完全的7.3.2頂點(diǎn)覆蓋、團(tuán)與獨(dú)立集設(shè)無7.3.2頂點(diǎn)覆蓋、團(tuán)與獨(dú)立集設(shè)無向圖G=<V,EVV.V是G的一個(gè)頂點(diǎn)覆蓋 G的每一條邊都至少有一個(gè)頂點(diǎn)在團(tuán)對(duì)任u,vV且uv,都有(u,v)E.獨(dú)立集對(duì)任u,vV,都有(u,v)E.中引理7.1對(duì)任意的無向圖G=<V,E>和子集VV,下述命題是等價(jià)的:(1)是G的頂點(diǎn)覆蓋VV是G的獨(dú)立集VV是補(bǔ)Gc=<V,Ec>的團(tuán)頂點(diǎn)覆蓋、團(tuán)與獨(dú)立集任頂點(diǎn)覆蓋、團(tuán)與獨(dú)立集任給一個(gè)無向圖G=<V,E>和非負(fù)整數(shù)頂點(diǎn)覆蓋問G有頂點(diǎn)數(shù)不超K的頂點(diǎn)覆蓋嗎團(tuán)任給一個(gè)無向圖G=<V,E>和非負(fù)整數(shù)J|V|問G有頂點(diǎn)數(shù)不小于J的團(tuán)嗎?獨(dú)立集任給一個(gè)G=<V,E>和非負(fù)J|V|問G頂點(diǎn)數(shù)不小于的獨(dú)立集嗎定理定理頂點(diǎn)覆蓋NP完全的獨(dú)立集和團(tuán)是NP完全的4哈密頓回路、4哈密頓回路、貨郎問題與恰好覆蓋有向哈密頓回路:任給有向圖D,問:D中有哈密頓回路嗎?定理7.12有向HC是NP完全的.定理7.13HC是NP完全的定理7.14TSP是NP完全的恰好覆蓋給定有A={a1,a2,,an}和A的子集的集合{S1,S2,,Sm},問:存在子集UW使得U中子集彼此不交且它們的并集等于A? 稱U是A的恰好覆蓋.例如設(shè)A={1,2,3,4,5S1={1,2S2={1,3,4},S3={2,4},則{S2,S4}是A的恰好覆蓋定理恰好覆蓋是NP完全的子集和、背包、裝箱與雙機(jī)調(diào)子集和、背包、裝箱與雙機(jī)調(diào)度子集和:給定正整數(shù)集合X={x1,x2,,xn}及正整數(shù)N,問存X的子集T,使得T中的元素之和等于N嗎裝箱給定n件物品物品j的重量為正整數(shù)wj,1jn以及箱子數(shù)K.規(guī)定每只箱子裝入物品的總重量不超過正整數(shù)B,問能用K只箱子裝入所有的物品嗎?雙機(jī)調(diào)度有2臺(tái)機(jī)器n項(xiàng)作J1,J2,,Jn,這2臺(tái)機(jī)器完相同每一項(xiàng)作業(yè)可以在任一臺(tái)機(jī)器上進(jìn)行沒有先后順序Ji的處理ti1in截止時(shí)間為ti在截止時(shí)都是正整數(shù),問能把n項(xiàng)作業(yè)分配給這2臺(tái)機(jī)器D內(nèi)完成所有的作業(yè)嗎NP完全性子集和是NPNP完全性子集和是NP完全的.0-1背包是NP完全的雙機(jī)調(diào)度是NP完全的裝箱是NP完全的定理定理7.17定理7.18定理注意0-1背包問題優(yōu)化形式的動(dòng)態(tài)規(guī)劃算法其時(shí)間復(fù)雜為O(nB),其中n是物品的個(gè)數(shù),B是重量限制.這不是多項(xiàng)時(shí)間算法,而是指數(shù)時(shí)間算法偽多項(xiàng)式時(shí)間算法算法的時(shí)間|I|max(I的某個(gè)二元多p(|I|max(I))為上界,其中max(I)是實(shí)I中數(shù)的最大絕對(duì)值.NP完全性NP完全性理論的應(yīng)用用NP完全性理論進(jìn)行子問題分析子問題的計(jì)算復(fù)雜性子問題的NP完全性證明NP難度搜索問Turing歸約NP-hard,NP-子問題的計(jì)算復(fù)子問題的計(jì)算復(fù)雜性?P努力擴(kuò)大已知區(qū)域，縮小未知區(qū)當(dāng)PNP時(shí)，存在不屬于NPC也不屬于P的問有先行約束多處理機(jī)有先行約束多處理機(jī)調(diào)度問題優(yōu)化問題給定任務(wù)Tm臺(tái)機(jī)器,tT,l(t)Z+,T上的偏序:T01D}滿足下述條件T為可行調(diào)度tT,(t)+l(t)i,0iD,|{tT:(t)i<(t)+l(t)}|(3)t,t?t’(t)+l(t)求使D最小的可行調(diào)度條件說明任務(wù)在截止時(shí)間前完成同時(shí)工作的臺(tái)數(shù)不m有偏序約束的任務(wù)必須按照約束先實(shí)112任務(wù)集如圖所D最小的可行調(diào)度求使得12實(shí)112任務(wù)集如圖所D最小的可行調(diào)度求使得121 判定問題實(shí)例：任務(wù)集T,m臺(tái)機(jī)器,tT,l(t)判定問題實(shí)例：任務(wù)集T,m臺(tái)機(jī)器,tT,l(t)Z+,T上的偏截止時(shí)問：是否存在小于等于的可行調(diào)度？子問題通過限制參數(shù)(機(jī)器數(shù)、工作時(shí)間、偏序)構(gòu)成參限偏樹任m大小m1,2,…,某個(gè)常數(shù)m任意l大小l為常l任意調(diào)度問題的子問題結(jié)構(gòu)從上到下：偏序任意、樹形偏序、無偏序約從調(diào)度問題的子問題結(jié)構(gòu)從上到下：偏序任意、樹形偏序、無偏序約從左到右：處理器臺(tái)數(shù)限制逐步放從前到后：各任務(wù)等長(zhǎng)工作時(shí)間、任意工作時(shí)l任意任意為樹m任意搜索問題與優(yōu)化問題的難度Turing歸約搜索問題與優(yōu)化問題的難度Turing歸約設(shè)1,2是搜索問題，A是利用解2的假想子程序s解1算法，且只要s是多項(xiàng)式時(shí)間的，A也是多項(xiàng)式時(shí)間的，A是從1到2的多項(xiàng)式時(shí)間Turing歸約.這時(shí)也稱算法1Turing歸約NP難度2，記1∝T2.設(shè)是搜索問題，如果存在NP完全問題’使得’T稱是NP-hard.這意味著在多項(xiàng)式可計(jì)算的角度看，至少和NPC問題一樣難.許多NP完全問題對(duì)應(yīng)的優(yōu)化問題都是NP-hard實(shí)例—證明NP等價(jià)例貨郎問題（TSO實(shí)例—證明NP等價(jià)例貨郎問題（TSO）是NP等價(jià)的證：易證TSON