第10章NP完全問題課件

110.1

引言10.2P類10.3NP類10.4NP完全問題10.5co-NP類(略)10.6NPI類(略)10.7四種類之間的關(guān)系(略)10.x

近似算法初步110.1引言210.1引言在前面的各章中，我們對(duì)一些算法的設(shè)計(jì)和分析進(jìn)行了討論，這些算法的運(yùn)行時(shí)間可用低次多項(xiàng)式來(lái)表示。在這一章，我們將注意力集中在這樣一類問題，這些問題至今沒有找到有效算法，而且今后也有可能證明它們不存在有效算法。設(shè)П是任意問題，如果對(duì)該問題存在一個(gè)算法，它的時(shí)間復(fù)雜性是O(nk)，其中n是輸入大小、k是非負(fù)整數(shù)，我們說(shuō)問題П存在多項(xiàng)式時(shí)間算法。現(xiàn)實(shí)世界的許多問題并不屬于這個(gè)范疇，因?yàn)榍蠼膺@些問題耗費(fèi)的時(shí)間需用指數(shù)函數(shù)或階乘函數(shù)來(lái)表示。210.1引言3⑴易求解問題存在多項(xiàng)式時(shí)間算法。⑵難解問題到目前為止不存在多項(xiàng)式時(shí)間算法。

本章將研究難解問題的一個(gè)子類，通常稱為NP完全問題(NPC問題)。這一類問題目前約有3000多個(gè)，其中還包括數(shù)百個(gè)著名問題。它們有一個(gè)共同特性，如果它們中的一個(gè)是多項(xiàng)式可解的話，那么所有其它問題也是多項(xiàng)式可解的。現(xiàn)存的求解這些問題算法的運(yùn)行時(shí)間，對(duì)于中等大小的輸入也要用幾百或幾千年的時(shí)間。3⑴易求解問題4⑶判定問題

為了研究問題的復(fù)雜性，我們必須將問題抽象。為了簡(jiǎn)化問題，我們只考慮一類簡(jiǎn)單的問題，稱為“判定性問題”。也就是說(shuō)提出一個(gè)問題，只需要回答Yes或者No。任何一般的最優(yōu)化問題都可以轉(zhuǎn)化為一系列判定性問題。例如，求圖中從結(jié)點(diǎn)A到結(jié)點(diǎn)B的最短路徑。該問題可以轉(zhuǎn)化成如下形式：從A到B是否有長(zhǎng)度為1的最短路徑？ No從A到B是否有長(zhǎng)度為2的最短路徑？ No………………………？ No從A到B是否有長(zhǎng)度為k-1的最短路徑？ No從A到B是否有長(zhǎng)度為k的最短路徑？ Yes

如果問到了k的時(shí)候，回答了Yes，則停止發(fā)問。我們可以說(shuō)，從結(jié)點(diǎn)A到結(jié)點(diǎn)B的最短路徑長(zhǎng)度為k。4⑶判定問題510.2P類⑴確定性算法定義10.1(Page176)

設(shè)A是求解問題П的一個(gè)算法。如果在展示問題П的一個(gè)實(shí)例時(shí)，在整個(gè)執(zhí)行過(guò)程中每一步都只有一種選擇，則稱A是確定性算法。因此對(duì)于同樣的輸入，實(shí)例一遍又一遍地執(zhí)行，它的輸出從不改變。在前面各章所討論的所有算法都是確定性的。給出一個(gè)無(wú)向圖G=(V,E)，它有哈密頓回路嗎？即在圖中是否存在一條恰好訪問每個(gè)結(jié)點(diǎn)一次的回路?？梢杂酶F舉法來(lái)求解，一條回路一條回路檢查下去，最終便能得到結(jié)果。但是窮舉法的算法時(shí)間復(fù)雜性是指數(shù)級(jí)的，計(jì)算時(shí)間隨問題規(guī)模成指數(shù)型增長(zhǎng)，問題很快就變得不可計(jì)算了，所以確定性算法對(duì)此類問題無(wú)效。510.2P類6⑵P類定義定義10.2(Page176)

判定問題的P類由這樣的判定問題組成，它們的Yes/No解可以用確定性算法在運(yùn)行多項(xiàng)式步數(shù)內(nèi)，例如在O(nk)步內(nèi)得到，其中k是某個(gè)非負(fù)整數(shù)，n是輸入大小。例1：給出一個(gè)有n個(gè)整數(shù)的表，它們是否按降序排列？答：只要檢查表中相鄰二個(gè)數(shù)即可，運(yùn)行時(shí)間為O(n)。例2：給出二個(gè)整數(shù)集合，它們的交集是否為空？答：先將所有整數(shù)排序，然后檢查相鄰二數(shù)是否相等，顯然運(yùn)行時(shí)間為O(nlog2n)。6⑵P類定義710.3NP類

有些計(jì)算問題是確定性的，例如“加減乘除”，你只要按照公式推導(dǎo)，按部就班一步步進(jìn)行，就可以得到結(jié)果。但是，有些問題無(wú)法按部就班直接進(jìn)行計(jì)算的。例如“找大質(zhì)數(shù)”問題，已知目前最大質(zhì)數(shù)，那么下一個(gè)大質(zhì)數(shù)應(yīng)該是多少呢？有沒有一個(gè)公式可以一步步推算出來(lái)，顯然這樣的公式是沒有的。這種問題的答案，是無(wú)法直接計(jì)算得到的，只能通過(guò)“猜算”來(lái)得到結(jié)果，這就是非確定性問題。這些問題通常有個(gè)算法，它不能直接告訴你答案是什么，但可以告訴你，某個(gè)可能的結(jié)果是正確的還是錯(cuò)誤的。這個(gè)可以告訴你“猜算”的答案正確與否的算法，稱為非確定性算法。假如“猜算”可以在多項(xiàng)式時(shí)間內(nèi)得到，那么該問題稱作“多項(xiàng)式非確定性問題”。710.3NP類8⑴非確定性算法對(duì)于輸入x，一個(gè)非確定性算法由猜測(cè)和驗(yàn)證二個(gè)階段組成。⑴猜測(cè)階段在這個(gè)階段產(chǎn)生一個(gè)任意字符串y，它可能對(duì)應(yīng)輸入實(shí)例的一個(gè)解，也可以不對(duì)應(yīng)解。事實(shí)上，它甚至可能不是所求解的合適形式，它可能在非確定算法的不同次運(yùn)行中不同。它僅要求在多項(xiàng)式步數(shù)內(nèi)產(chǎn)生這個(gè)串，即在O(ni)時(shí)間內(nèi)，這里n=|x|，i是非負(fù)整數(shù)。對(duì)于許多問題，這一階段可以在線性時(shí)間內(nèi)完成。⑵驗(yàn)證階段首先檢查產(chǎn)生的解串y是否有合適的形式，如果不是，則算法停下來(lái)并回答No；如果y是合適形式，那么算法繼續(xù)檢查它是否是問題實(shí)例x的解。若是，則算法停下來(lái)并回答Yes；否則算法停下來(lái)并回答No。我們也要求這個(gè)階段在多項(xiàng)式步數(shù)內(nèi)完成，即在O(nj)時(shí)間內(nèi)，這里j是一個(gè)非負(fù)整數(shù)。非確定性算法的運(yùn)行時(shí)間是由猜測(cè)階段和驗(yàn)證階段二部分耗費(fèi)時(shí)間組成，因此它是O(nk)=O(ni)+O(nj)，k是某個(gè)非負(fù)整數(shù)。8⑴非確定性算法9

例：求大整數(shù)n的一個(gè)真因數(shù)(即1和n本身以外的一個(gè)因數(shù)，并且該因數(shù)是素?cái)?shù))。這是一個(gè)至今未能找到有效算法的難解問題。對(duì)于難解問題，人們除了使用傳統(tǒng)型計(jì)算方法外，又想出了另一種類型的計(jì)算方法，該方法稱為“非確定性算法”。傳說(shuō)從前有位年輕的國(guó)王，想求出整數(shù)190334261410902619的一個(gè)真因素。他用2、3、5、7、11、13、……這些素?cái)?shù)逐一去試，化了九牛二虎之力也無(wú)法算出，于是他把這個(gè)問題交給了宰相。國(guó)王用的計(jì)算方法稱為“窮舉法”，是一種傳統(tǒng)的計(jì)算方法，窮舉法屬“確定性算法”。9例：求大整數(shù)n的一個(gè)真因數(shù)(即1和n本身以外的一個(gè)10

宰相猜想這個(gè)數(shù)可能是9位整數(shù)，于是宰相把全國(guó)成年百姓編成十個(gè)軍，每個(gè)軍有十個(gè)師，每個(gè)師有十個(gè)旅，每個(gè)旅有十個(gè)團(tuán)，每個(gè)團(tuán)有十個(gè)營(yíng)，每個(gè)營(yíng)有十個(gè)連，每個(gè)連有十個(gè)排，每個(gè)排有十個(gè)班，每個(gè)班有十個(gè)組，每個(gè)組有十個(gè)人，于是每個(gè)成年百姓都具有一個(gè)9位的番號(hào)。然后把題目發(fā)下去，讓每個(gè)成年百姓用自己的番號(hào)去除“190334261410902619”這個(gè)數(shù)，若除盡了就把番號(hào)報(bào)上來(lái)。很快就有二個(gè)人報(bào)上了結(jié)果，即“436273009”與“436273291”。經(jīng)國(guó)王驗(yàn)證，這二個(gè)整數(shù)都是素?cái)?shù)，并且這二個(gè)整數(shù)的積就是題目所給的18位整數(shù)。10宰相猜想這個(gè)數(shù)可能是9位整數(shù)，于是宰相把全國(guó)成年11190334261410902619436273009 *436273291軍師旅團(tuán)營(yíng)連排組人軍師旅團(tuán)營(yíng)連排組人=這個(gè)故事說(shuō)明算法分析中最基本問題：求大整數(shù)的真因數(shù)不能用多項(xiàng)式時(shí)間求解，但是驗(yàn)證某數(shù)是否是大整數(shù)的真因數(shù)可以用多項(xiàng)式時(shí)間完成。所以，求大整數(shù)的真因數(shù)要比驗(yàn)證真因數(shù)要難得多；國(guó)王用得是確定性計(jì)算方法(窮舉法)，所以計(jì)算很快變得無(wú)法進(jìn)行下去；宰相用得是非確定性計(jì)算方法，首先猜想，然后驗(yàn)證。1119033426141090261943612⑵NP類定義定義10.3(Page177)

NP類是由這樣的判定問題組成：對(duì)于它們存在多項(xiàng)式時(shí)間內(nèi)運(yùn)行的非確定性算法。㈢P類和NP類的區(qū)別P類是一個(gè)判定問題類，這些問題可以用一個(gè)確定性算法，在多項(xiàng)式時(shí)間內(nèi)判定或解出；NP類是一個(gè)判定問題類，這些問題可以用一個(gè)確定性算法，在多項(xiàng)式時(shí)間內(nèi)檢查或驗(yàn)證它們的解。12⑵NP類定義1310.4NP完全問題定義10.4(Page178)

設(shè)∏和∏'是二個(gè)判定問題。如果存在一個(gè)確定性算法A，它的行為如下：當(dāng)給A展示問題∏的一個(gè)實(shí)例I，算法A可以把它變換為問題∏'的實(shí)例I'。當(dāng)且僅當(dāng)對(duì)I'回答yes時(shí)，對(duì)I回答Yes，而且這個(gè)變換在多項(xiàng)式時(shí)間內(nèi)完成。那么我們說(shuō)∏可以在多項(xiàng)式時(shí)間內(nèi)歸約到∏'，用符號(hào)∏∝poly∏'表示。定理10.3(Page178)

設(shè)∏、∏'和∏"是三個(gè)判定問題，有∏∝poly∏'和∏'∝poly∏"，那么∏∝poly∏"。推論10.1(Page179)

如果∏和∏'是NP中的二個(gè)問題，若有∏'∝poly∏，并且∏'是完全的，則∏是完全的。1310.4NP完全問題14

如果一個(gè)NP問題的所有可能答案，都可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行正確與否驗(yàn)證的話，那么該問題稱為“完全多項(xiàng)式非確定性問題”，簡(jiǎn)稱NP完全問題或NPC問題。NP完全問題是NP類的一個(gè)子類。這是對(duì)“NP完全問題”的一個(gè)比較通俗的解釋，對(duì)于初學(xué)者來(lái)說(shuō)比較容易理解，上頁(yè)則給出了“NP完全問題”的嚴(yán)格定義。例10.5考慮下面二個(gè)問題(Page179)⑴哈密頓回路問題：給出一個(gè)無(wú)向圖G=(V,E)，它有哈密頓回路嗎？即在圖中存在一條恰好訪問每個(gè)結(jié)點(diǎn)一次的回路。⑵旅行商問題：給出一個(gè)n個(gè)城市集合，且給出城市間的距離。對(duì)于一個(gè)整數(shù)k，是否存在最長(zhǎng)為k的游程？這里，一條游程是一個(gè)回路，它恰好訪問每個(gè)城市一次。眾所周知，哈密頓回路問題是NPC問題。根據(jù)這一事實(shí)我們來(lái)證明旅行商問題也是NPC問題。14如果一個(gè)NP問題的所有可能答案，都可以在多項(xiàng)式時(shí)15㈠證明：旅行商問題是NP問題使用非確定性算法，先猜測(cè)一個(gè)城市序列，然后驗(yàn)證這個(gè)序列是一個(gè)游程。如果是，只要判斷游程的長(zhǎng)度是否超過(guò)界k即可。㈡證明：哈密頓回路問題在多項(xiàng)式時(shí)間內(nèi)歸約到旅行商問題設(shè)G是哈密頓回路的任意實(shí)例。我們構(gòu)建一個(gè)含權(quán)圖G'和一個(gè)界k，使得當(dāng)且僅當(dāng)G'有一個(gè)總長(zhǎng)不超過(guò)k的游程時(shí)，G有一條哈密頓回路。設(shè)G=(V,E)，G'=(V,E')是結(jié)點(diǎn)V集合上的完全圖，即

E'={(u,v)|u,v∈V}

給E'中的每條邊的長(zhǎng)度定義如下：

其中n=|V|，且指派k=n。從構(gòu)建中可以看到，當(dāng)且僅當(dāng)G'有一個(gè)長(zhǎng)度恰好為n的游程時(shí)，G有一條哈密頓回路。由此可得：哈密頓回路問題∝poly旅行商問題15㈠證明：旅行商問題是NP問題其中n=|V|，且指16NPC問題可以用窮舉法來(lái)求解，對(duì)于可能解一個(gè)個(gè)檢查下去，最終便能得到結(jié)果。但是隨著問題規(guī)模增大，計(jì)算時(shí)間成指數(shù)型增長(zhǎng)，很快變得不可計(jì)算了。如果給出一個(gè)回路，我們很容易判斷它是否是哈密頓回路。只要檢查所有的結(jié)點(diǎn)是否都在這個(gè)回路中，并且只出現(xiàn)一次。檢查僅需O(n2)時(shí)間。我們一般認(rèn)為NPC問題是難解問題。因?yàn)榈侥壳盀橹梗鼈冞€不存在一個(gè)多項(xiàng)式時(shí)間的算法，甚至將來(lái)也很難找到，即P≠NP。實(shí)際上，對(duì)于某些結(jié)點(diǎn)數(shù)不到100的無(wú)向圖，使用現(xiàn)有速度最快的計(jì)算機(jī)也需要比較荒唐的時(shí)間，例如耗費(fèi)幾百年才能夠確定它是否存在一條哈密頓回路。16NPC問題可以用窮舉法來(lái)求解，對(duì)于可能解一個(gè)個(gè)檢17

庫(kù)克在1971年找到了第一個(gè)NP完全問題，即可滿足性問題(邏輯運(yùn)算問題)。此后，人們又陸續(xù)發(fā)現(xiàn)很多NP完全問題。例如，哈密頓回路問題、旅行商問題、圖的3著色問題、多處理機(jī)調(diào)度問題、……。 人們發(fā)現(xiàn)，所有的NP完全問題都可以在多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)換到可滿足性問題。只要它們中的一個(gè)，如果存在“多項(xiàng)式時(shí)間確定性算法”的話，那么NPC問題中的所有問題，都可以用“多項(xiàng)式時(shí)間確定性算法”來(lái)求解。 人們于是就猜想，既然NPC問題的所有可能解，都可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證，對(duì)于此類問題是否存在一個(gè)確定性算法，可以在多項(xiàng)式時(shí)間內(nèi)直接給出解呢？這就是著名的NP=P?的猜想。這是21世紀(jì)計(jì)算機(jī)科學(xué)家向數(shù)學(xué)家提出的世界難題。17庫(kù)克在1971年找到了第一個(gè)NP完全問題，即可滿18

解決NP=P?的猜想無(wú)非兩種可能。一種是找到一個(gè)這樣的算法，只要針對(duì)某個(gè)特定NP完全問題找到一個(gè)算法，所有這類問題都可以迎刃而解了，因?yàn)樗鼈兛梢赞D(zhuǎn)化為同一個(gè)問題。另外的一種可能，就是這樣的算法是不存在的。那么，就要從數(shù)學(xué)理論上證明它為什么不存在。 前段時(shí)間轟動(dòng)世界的一個(gè)數(shù)學(xué)成果，是幾個(gè)印度人提出了一個(gè)新算法。該算法可以在多項(xiàng)式時(shí)間內(nèi)，證明某個(gè)數(shù)是或者不是質(zhì)數(shù)。而在這之前，人們認(rèn)為質(zhì)數(shù)的證明是個(gè)非多項(xiàng)式問題?？梢姡行┛磥?lái)好象是非多項(xiàng)式問題，其實(shí)是多項(xiàng)式問題，只是人們目前還不知道它的多項(xiàng)式解而已。18解決NP=P?的猜想無(wú)非兩種可能。一種是找到一個(gè)1910.x近似算法初步在現(xiàn)實(shí)世界中，存在大量NP難解問題。這些問題在理論上是可解的，但求解這些問題的時(shí)間需要用指數(shù)函數(shù)和階乘函數(shù)來(lái)描述。非常有趣的是，它們中的許多問題是普通的自然問題，其中還包括了數(shù)百個(gè)著名問題，例圖的3著色問題、哈密頓回路問題、……。到目前為止，人們還不知道它們是否存在多項(xiàng)式時(shí)間算法?，F(xiàn)存的求解這些問題算法的運(yùn)行時(shí)間，對(duì)于中等規(guī)模大小的輸入，也要用幾百年或幾千年來(lái)度量。為了走出這一困境，人們一方面試圖擺脫馮·諾依曼計(jì)算機(jī)體系結(jié)構(gòu)，研究新一代計(jì)算機(jī)體系結(jié)構(gòu)；另一方面，仍在馮·諾依曼計(jì)算機(jī)體系結(jié)下來(lái)尋求解決這類問題的可行辦法。解決這些問題的思路是：與其耗費(fèi)令人難以接受的大量時(shí)間去尋找精確解，倒不如用較少時(shí)間去尋找近似解。1910.x近似算法初步20

在求解一個(gè)問題時(shí)，也許最先出現(xiàn)在你腦海中的策略是貪心方法。例如背包問題，可使用下面貪心策略來(lái)近似求解。設(shè)yi=vi/si(性價(jià)比=價(jià)值/容積)，將物品按y值的大小降序排列。從第一項(xiàng)開始裝背包，然后第二項(xiàng)，盡可能多裝，直至背包不能容納余下的物品為止。背包問題描述如下：

U={u1,u2,u3,u4} S={s1,s2,s3,s4}={2,3,4,5} V={v1,v2,v3,v4}={3,4,5,8} Y={v4/s4,v1/s1,v2/s2,v3/s3}={1.60,1.50,1.33,1.25} C=9精確解：在背包中裝入物品u3和u4，總價(jià)值為最大值13。近似解：重新排列物品，使得U={u4,u1,u2,u3}。按上述策略，裝入物品u4和u1，總價(jià)值為11。20在求解一個(gè)問題時(shí)，也許最先出現(xiàn)在你腦海中的策略是21背包問題近似算法輸入：背包容量C、物品體積集合S={s1,s2,...,sn}、物品價(jià)值集合V={v1,v2,...,vn}。輸出：裝入背包中物品集合Z和總價(jià)值V，Z的總體積最多為C。1.重新排列物品U，使得y1≥y2≥…≥yn(yi=vi/si)。2．j←0；K←0；V←0；Z←{}3.while(j<n)and(K<C)4. j←j+15. ifsj≤C-Kthen6. Z←Z∪{uj} //Z表示裝入背包中物品集合7. K←K+sj

//K表示裝入背包中物品的總體積8. V←V+vj //V表示裝入背包中物品所具有的價(jià)值7. endif8.endwhile9.outputZ10.outputV

上述算法主要耗費(fèi)在性價(jià)比Y的排序上，所以背包問題近似解的時(shí)間復(fù)雜性可用O(nlog2n)來(lái)描述。21背包問題近似算法2210.1

引言10.2P類10.3NP類10.4NP完全問題10.5co-NP類(略)10.6NPI類(略)10.7四種類之間的關(guān)系(略)10.x

近似算法初步110.1引言2310.1引言在前面的各章中，我們對(duì)一些算法的設(shè)計(jì)和分析進(jìn)行了討論，這些算法的運(yùn)行時(shí)間可用低次多項(xiàng)式來(lái)表示。在這一章，我們將注意力集中在這樣一類問題，這些問題至今沒有找到有效算法，而且今后也有可能證明它們不存在有效算法。設(shè)П是任意問題，如果對(duì)該問題存在一個(gè)算法，它的時(shí)間復(fù)雜性是O(nk)，其中n是輸入大小、k是非負(fù)整數(shù)，我們說(shuō)問題П存在多項(xiàng)式時(shí)間算法。現(xiàn)實(shí)世界的許多問題并不屬于這個(gè)范疇，因?yàn)榍蠼膺@些問題耗費(fèi)的時(shí)間需用指數(shù)函數(shù)或階乘函數(shù)來(lái)表示。210.1引言24⑴易求解問題存在多項(xiàng)式時(shí)間算法。⑵難解問題到目前為止不存在多項(xiàng)式時(shí)間算法。

本章將研究難解問題的一個(gè)子類，通常稱為NP完全問題(NPC問題)。這一類問題目前約有3000多個(gè)，其中還包括數(shù)百個(gè)著名問題。它們有一個(gè)共同特性，如果它們中的一個(gè)是多項(xiàng)式可解的話，那么所有其它問題也是多項(xiàng)式可解的?，F(xiàn)存的求解這些問題算法的運(yùn)行時(shí)間，對(duì)于中等大小的輸入也要用幾百或幾千年的時(shí)間。3⑴易求解問題25⑶判定問題

為了研究問題的復(fù)雜性，我們必須將問題抽象。為了簡(jiǎn)化問題，我們只考慮一類簡(jiǎn)單的問題，稱為“判定性問題”。也就是說(shuō)提出一個(gè)問題，只需要回答Yes或者No。任何一般的最優(yōu)化問題都可以轉(zhuǎn)化為一系列判定性問題。例如，求圖中從結(jié)點(diǎn)A到結(jié)點(diǎn)B的最短路徑。該問題可以轉(zhuǎn)化成如下形式：從A到B是否有長(zhǎng)度為1的最短路徑？ No從A到B是否有長(zhǎng)度為2的最短路徑？ No………………………？ No從A到B是否有長(zhǎng)度為k-1的最短路徑？ No從A到B是否有長(zhǎng)度為k的最短路徑？ Yes

如果問到了k的時(shí)候，回答了Yes，則停止發(fā)問。我們可以說(shuō)，從結(jié)點(diǎn)A到結(jié)點(diǎn)B的最短路徑長(zhǎng)度為k。4⑶判定問題2610.2P類⑴確定性算法定義10.1(Page176)

設(shè)A是求解問題П的一個(gè)算法。如果在展示問題П的一個(gè)實(shí)例時(shí)，在整個(gè)執(zhí)行過(guò)程中每一步都只有一種選擇，則稱A是確定性算法。因此對(duì)于同樣的輸入，實(shí)例一遍又一遍地執(zhí)行，它的輸出從不改變。在前面各章所討論的所有算法都是確定性的。給出一個(gè)無(wú)向圖G=(V,E)，它有哈密頓回路嗎？即在圖中是否存在一條恰好訪問每個(gè)結(jié)點(diǎn)一次的回路?？梢杂酶F舉法來(lái)求解，一條回路一條回路檢查下去，最終便能得到結(jié)果。但是窮舉法的算法時(shí)間復(fù)雜性是指數(shù)級(jí)的，計(jì)算時(shí)間隨問題規(guī)模成指數(shù)型增長(zhǎng)，問題很快就變得不可計(jì)算了，所以確定性算法對(duì)此類問題無(wú)效。510.2P類27⑵P類定義定義10.2(Page176)

判定問題的P類由這樣的判定問題組成，它們的Yes/No解可以用確定性算法在運(yùn)行多項(xiàng)式步數(shù)內(nèi)，例如在O(nk)步內(nèi)得到，其中k是某個(gè)非負(fù)整數(shù)，n是輸入大小。例1：給出一個(gè)有n個(gè)整數(shù)的表，它們是否按降序排列？答：只要檢查表中相鄰二個(gè)數(shù)即可，運(yùn)行時(shí)間為O(n)。例2：給出二個(gè)整數(shù)集合，它們的交集是否為空？答：先將所有整數(shù)排序，然后檢查相鄰二數(shù)是否相等，顯然運(yùn)行時(shí)間為O(nlog2n)。6⑵P類定義2810.3NP類

有些計(jì)算問題是確定性的，例如“加減乘除”，你只要按照公式推導(dǎo)，按部就班一步步進(jìn)行，就可以得到結(jié)果。但是，有些問題無(wú)法按部就班直接進(jìn)行計(jì)算的。例如“找大質(zhì)數(shù)”問題，已知目前最大質(zhì)數(shù)，那么下一個(gè)大質(zhì)數(shù)應(yīng)該是多少呢？有沒有一個(gè)公式可以一步步推算出來(lái)，顯然這樣的公式是沒有的。這種問題的答案，是無(wú)法直接計(jì)算得到的，只能通過(guò)“猜算”來(lái)得到結(jié)果，這就是非確定性問題。這些問題通常有個(gè)算法，它不能直接告訴你答案是什么，但可以告訴你，某個(gè)可能的結(jié)果是正確的還是錯(cuò)誤的。這個(gè)可以告訴你“猜算”的答案正確與否的算法，稱為非確定性算法。假如“猜算”可以在多項(xiàng)式時(shí)間內(nèi)得到，那么該問題稱作“多項(xiàng)式非確定性問題”。710.3NP類29⑴非確定性算法對(duì)于輸入x，一個(gè)非確定性算法由猜測(cè)和驗(yàn)證二個(gè)階段組成。⑴猜測(cè)階段在這個(gè)階段產(chǎn)生一個(gè)任意字符串y，它可能對(duì)應(yīng)輸入實(shí)例的一個(gè)解，也可以不對(duì)應(yīng)解。事實(shí)上，它甚至可能不是所求解的合適形式，它可能在非確定算法的不同次運(yùn)行中不同。它僅要求在多項(xiàng)式步數(shù)內(nèi)產(chǎn)生這個(gè)串，即在O(ni)時(shí)間內(nèi)，這里n=|x|，i是非負(fù)整數(shù)。對(duì)于許多問題，這一階段可以在線性時(shí)間內(nèi)完成。⑵驗(yàn)證階段首先檢查產(chǎn)生的解串y是否有合適的形式，如果不是，則算法停下來(lái)并回答No；如果y是合適形式，那么算法繼續(xù)檢查它是否是問題實(shí)例x的解。若是，則算法停下來(lái)并回答Yes；否則算法停下來(lái)并回答No。我們也要求這個(gè)階段在多項(xiàng)式步數(shù)內(nèi)完成，即在O(nj)時(shí)間內(nèi)，這里j是一個(gè)非負(fù)整數(shù)。非確定性算法的運(yùn)行時(shí)間是由猜測(cè)階段和驗(yàn)證階段二部分耗費(fèi)時(shí)間組成，因此它是O(nk)=O(ni)+O(nj)，k是某個(gè)非負(fù)整數(shù)。8⑴非確定性算法30

例：求大整數(shù)n的一個(gè)真因數(shù)(即1和n本身以外的一個(gè)因數(shù)，并且該因數(shù)是素?cái)?shù))。這是一個(gè)至今未能找到有效算法的難解問題。對(duì)于難解問題，人們除了使用傳統(tǒng)型計(jì)算方法外，又想出了另一種類型的計(jì)算方法，該方法稱為“非確定性算法”。傳說(shuō)從前有位年輕的國(guó)王，想求出整數(shù)190334261410902619的一個(gè)真因素。他用2、3、5、7、11、13、……這些素?cái)?shù)逐一去試，化了九牛二虎之力也無(wú)法算出，于是他把這個(gè)問題交給了宰相。國(guó)王用的計(jì)算方法稱為“窮舉法”，是一種傳統(tǒng)的計(jì)算方法，窮舉法屬“確定性算法”。9例：求大整數(shù)n的一個(gè)真因數(shù)(即1和n本身以外的一個(gè)31

宰相猜想這個(gè)數(shù)可能是9位整數(shù)，于是宰相把全國(guó)成年百姓編成十個(gè)軍，每個(gè)軍有十個(gè)師，每個(gè)師有十個(gè)旅，每個(gè)旅有十個(gè)團(tuán)，每個(gè)團(tuán)有十個(gè)營(yíng)，每個(gè)營(yíng)有十個(gè)連，每個(gè)連有十個(gè)排，每個(gè)排有十個(gè)班，每個(gè)班有十個(gè)組，每個(gè)組有十個(gè)人，于是每個(gè)成年百姓都具有一個(gè)9位的番號(hào)。然后把題目發(fā)下去，讓每個(gè)成年百姓用自己的番號(hào)去除“190334261410902619”這個(gè)數(shù)，若除盡了就把番號(hào)報(bào)上來(lái)。很快就有二個(gè)人報(bào)上了結(jié)果，即“436273009”與“436273291”。經(jīng)國(guó)王驗(yàn)證，這二個(gè)整數(shù)都是素?cái)?shù)，并且這二個(gè)整數(shù)的積就是題目所給的18位整數(shù)。10宰相猜想這個(gè)數(shù)可能是9位整數(shù)，于是宰相把全國(guó)成年32190334261410902619436273009 *436273291軍師旅團(tuán)營(yíng)連排組人軍師旅團(tuán)營(yíng)連排組人=這個(gè)故事說(shuō)明算法分析中最基本問題：求大整數(shù)的真因數(shù)不能用多項(xiàng)式時(shí)間求解，但是驗(yàn)證某數(shù)是否是大整數(shù)的真因數(shù)可以用多項(xiàng)式時(shí)間完成。所以，求大整數(shù)的真因數(shù)要比驗(yàn)證真因數(shù)要難得多；國(guó)王用得是確定性計(jì)算方法(窮舉法)，所以計(jì)算很快變得無(wú)法進(jìn)行下去；宰相用得是非確定性計(jì)算方法，首先猜想，然后驗(yàn)證。1119033426141090261943633⑵NP類定義定義10.3(Page177)

NP類是由這樣的判定問題組成：對(duì)于它們存在多項(xiàng)式時(shí)間內(nèi)運(yùn)行的非確定性算法。㈢P類和NP類的區(qū)別P類是一個(gè)判定問題類，這些問題可以用一個(gè)確定性算法，在多項(xiàng)式時(shí)間內(nèi)判定或解出；NP類是一個(gè)判定問題類，這些問題可以用一個(gè)確定性算法，在多項(xiàng)式時(shí)間內(nèi)檢查或驗(yàn)證它們的解。12⑵NP類定義3410.4NP完全問題定義10.4(Page178)

設(shè)∏和∏'是二個(gè)判定問題。如果存在一個(gè)確定性算法A，它的行為如下：當(dāng)給A展示問題∏的一個(gè)實(shí)例I，算法A可以把它變換為問題∏'的實(shí)例I'。當(dāng)且僅當(dāng)對(duì)I'回答yes時(shí)，對(duì)I回答Yes，而且這個(gè)變換在多項(xiàng)式時(shí)間內(nèi)完成。那么我們說(shuō)∏可以在多項(xiàng)式時(shí)間內(nèi)歸約到∏'，用符號(hào)∏∝poly∏'表示。定理10.3(Page178)

設(shè)∏、∏'和∏"是三個(gè)判定問題，有∏∝poly∏'和∏'∝poly∏"，那么∏∝poly∏"。推論10.1(Page179)

如果∏和∏'是NP中的二個(gè)問題，若有∏'∝poly∏，并且∏'是完全的，則∏是完全的。1310.4NP完全問題35

如果一個(gè)NP問題的所有可能答案，都可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行正確與否驗(yàn)證的話，那么該問題稱為“完全多項(xiàng)式非確定性問題”，簡(jiǎn)稱NP完全問題或NPC問題。NP完全問題是NP類的一個(gè)子類。這是對(duì)“NP完全問題”的一個(gè)比較通俗的解釋，對(duì)于初學(xué)者來(lái)說(shuō)比較容易理解，上頁(yè)則給出了“NP完全問題”的嚴(yán)格定義。例10.5考慮下面二個(gè)問題(Page179)⑴哈密頓回路問題：給出一個(gè)無(wú)向圖G=(V,E)，它有哈密頓回路嗎？即在圖中存在一條恰好訪問每個(gè)結(jié)點(diǎn)一次的回路。⑵旅行商問題：給出一個(gè)n個(gè)城市集合，且給出城市間的距離。對(duì)于一個(gè)整數(shù)k，是否存在最長(zhǎng)為k的游程？這里，一條游程是一個(gè)回路，它恰好訪問每個(gè)城市一次。眾所周知，哈密頓回路問題是NPC問題。根據(jù)這一事實(shí)我們來(lái)證明旅行商問題也是NPC問題。14如果一個(gè)NP問題的所有可能答案，都可以在多項(xiàng)式時(shí)36㈠證明：旅行商問題是NP問題使用非確定性算法，先猜測(cè)一個(gè)城市序列，然后驗(yàn)證這個(gè)序列是一個(gè)游程。如果是，只要判斷游程的長(zhǎng)度是否超過(guò)界k即可。㈡證明：哈密頓回路問題在多項(xiàng)式時(shí)間內(nèi)歸約到旅行商問題設(shè)G是哈密頓回路的任意實(shí)例。我們構(gòu)建一個(gè)含權(quán)圖G'和一個(gè)界k，使得當(dāng)且僅當(dāng)G'有一個(gè)總長(zhǎng)不超過(guò)k的游程時(shí)，G有一條哈密頓回路。設(shè)G=(V,E)，G'=(V,E')是結(jié)點(diǎn)V集合上的完全圖，即

E'={(u,v)|u,v∈V}

給E'中的每條邊的長(zhǎng)度定義如下：

其中n=|V|，且指派k=n。從構(gòu)建中可以看到，當(dāng)且僅當(dāng)G'有一個(gè)長(zhǎng)度恰好為n的游程時(shí)，G有一條哈密頓回路。由此可得：哈密頓回路問題∝poly旅行商問題15㈠證明：旅行商問題是NP問題其中n=|V|，且指37NPC問題可以用窮舉法來(lái)求解，對(duì)于可能解一個(gè)個(gè)檢查下去，最終便能得到結(jié)果。但是隨著問題規(guī)模增大，計(jì)算時(shí)間成指數(shù)型增長(zhǎng)，很快變得不可計(jì)算了。如果給出一個(gè)回路，我們很容易判斷它是否是哈密頓回路。只要檢查所有的結(jié)點(diǎn)是否都在這個(gè)回路中，并且只出現(xiàn)一次。檢查僅需O(n2)時(shí)間。我們一般認(rèn)為NPC問題是難解問題。因?yàn)榈侥壳盀橹?，它們還不存在一個(gè)多項(xiàng)式時(shí)間的算法，甚至將來(lái)也很難找到，即P≠NP。實(shí)際上，對(duì)于某些結(jié)點(diǎn)數(shù)不到100的無(wú)向圖，使用現(xiàn)有速度最快的計(jì)算機(jī)也需要比較荒唐的時(shí)間，例如耗費(fèi)幾百年才能夠確定它是否存在一條哈密頓回路。16NPC問題可以用窮舉法來(lái)求解，對(duì)于可能解一個(gè)個(gè)檢38

庫(kù)克在1971年找到了第一個(gè)NP完全問題，即可滿足性問題(邏輯運(yùn)算問題)。此后，人們又陸續(xù)發(fā)現(xiàn)很多NP完全問題。例如，哈密頓回路問題、旅行商問題、圖的3著色問題、多處理機(jī)調(diào)度問題、……。 人們發(fā)現(xiàn)，所有的NP完全問題都可以在多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)換到可滿足性問題。只要它們中的一個(gè)，如果存在“多項(xiàng)式時(shí)間確定性算法”的話，那么NPC問題中的所有問題，都可以用“多項(xiàng)式時(shí)間確定性算法”來(lái)求解。 人們于是就猜想，既然NPC問題的所有可能解，都可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證，對(duì)于此類問題是否存在一個(gè)確定性算法，可以在多項(xiàng)式時(shí)間內(nèi)直接給出解呢？這就是著名的NP=P?的猜想。這是21世紀(jì)計(jì)算機(jī)科學(xué)家向數(shù)學(xué)家提出的世界難題。17庫(kù)克在1971年找到了第一個(gè)NP完全問題，即可滿39

解決NP=P?的猜想無(wú)非兩種可能。一種是找到一個(gè)這樣的算法，只要針對(duì)某個(gè)特定NP完全問題找到一個(gè)算法，所有這類問題都可以迎刃而解了，因?yàn)樗鼈兛梢赞D(zhuǎn)化為同一個(gè)問題。另外的一種可能，就是這樣的算法是不存在的。那么，就要從數(shù)學(xué)理論上證明它為什么不存在。 前段時(shí)間轟動(dòng)世界的一個(gè)數(shù)學(xué)成果，是幾個(gè)印度人提出了一個(gè)新算法。該算法可以在多項(xiàng)式時(shí)間內(nèi)，證明某個(gè)數(shù)是或者不是質(zhì)數(shù)。而在這之前，人們認(rèn)為質(zhì)數(shù)的證明是個(gè)非多項(xiàng)式問題?？梢姡行┛磥?lái)好象是非多項(xiàng)式問題，其