第10章NP完全問題課件

110.1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

給E'中的每條邊的長度定義如下：

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

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

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

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

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，總價值為最大值13。近似解：重新排列物品，使得U={u4,u1,u2,u3}。按上述策略，裝入物品u4和u1，總價值為11。20在求解一個問題時，也許最先出現(xiàn)在你腦海中的策略是21背包問題近似算法輸入：背包容量C、物品體積集合S={s1,s2,...,sn}、物品價值集合V={v1,v2,...,vn}。輸出：裝入背包中物品集合Z和總價值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表示裝入背包中物品所具有的價值7. endif8.endwhile9.outputZ10.outputV

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

給E'中的每條邊的長度定義如下：

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

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

解決NP=P?的猜想無非兩種可能。一種是找到一個這樣的算法，只要針對某個特定NP完全問題找到一個算法，所有這類問題都可以迎刃而解了，因為它們可以轉(zhuǎn)化為同一個問題。另外的一種可能，就是這樣的算法是不存在的。那么，就要從數(shù)學理論上證明它為什么不存在。 前段時間轟動世界的一個數(shù)學成果，是幾個印度人提出了一個新算法。該算法可以在多項式時間內(nèi)，證明某個數(shù)是或者不是質(zhì)數(shù)。而在這之前，人們認為質(zhì)數(shù)的證明是個非多項式問題?？梢?，有些看來好象是非多項式問題，其