《算法設計與分析》課件第8章

第8章NP完全性8.1

P類問題和NP類問題

8.2

NP完全性

8.3典型的NP完全問題

習題 8.1

P類問題和NP類問題

引理8.1假設計算模型為RAM模型。如果對于某些常數c>0，一個c增量的算法A最壞情況下的運行時間為輸入項數N的函數t(N)，那么算法A的運行時間可表示為n的函數O(n2t(n))，其中n為輸入的非一元標準編碼串的位數。

證明：由于N≤n，因而t(N)≤t(n)。如果對于某些常數d≥1，算法A中的每個基本運算包含b(b≥1)位表示的一個或兩個對象，則至多利用db2個位就可完成每個基本運算。這些基本運算包括所有比較、控制流和基本的非乘法的算術運算。然而，在c增量算法的N步中，對于輸入對象的任一最大規(guī)模b，表示其中任一對象所用的最大位數為cN+b，而cN+b≤(c+1)n。因此，完成A中的每一步至多需要O(n2)位。證畢。

由此可得，如果一個合理算法的運行時間是輸入項數N的多項式時間，那么它也是輸入位數n的多項式時間。因此，本章其余部分中，我們用n作為問題的輸入規(guī)模，將多項式算法的運行時間理解為輸入位數的多項式函數。8.1.1復雜類P和復雜類NP

1．判定問題(decisionproblem)

為了簡化討論，暫時只討論判定問題，即輸出為“yes”或者“no”的計算問題。換句話說，判定問題的輸出只有一位，或者為0,或者為1。例如，下列每個問題都是判定問題。

·給定串S和串S1，S1是否是S的子串？

·給定兩個集合S和T，S和T是否包含相同元素?

·給定具有正權值邊的圖G及一個整數k，G中存在權值至多為k的最小生成樹嗎？

2．問題和語言

如果輸入為x的算法A輸出“yes”，我們說這個算法A接受輸入串x。因而，可以把判定問題只看做串的集合L，即正確解決那個問題的算法所能接受串的集合。而我們常常稱串的集合為語言(language)，所以用字母“L”表示判定問題。可以進一步擴展這個基于語言的觀點：如果對于L中的每個x，算法A輸出“yes”，則稱算法A接受語言L；否則，算法輸出“no”。這里需要注意的是，某些教材上允許算法A有進入無限循環(huán)的可能性，對于某些輸入不產生任何輸出，但這里我們只關注計算在有限步內終止的算法。

3．復雜類P

復雜類P(complexityclassP)是指所有判定問題(或者語言)L的集合，L是一個最壞情況為多項式時間被接受的語言，即對于輸入x∈L，存在算法A在p(n)時間內輸出“yes”，

其中n是x的規(guī)模，p(n)是多項式。這里需要注意的是，P的定義并沒有表明拒絕一個輸入所需的運行時間，即P的定義中沒有表明算法A輸出“no”時的運行時間。這種情況涉及語

言L的補(complement)，它是由不在L中的所有二進制串組成的。如果給定多項式時間p(n)接受語言L的算法A，我們仍然可以容易地構造一個接受語言L的補的多項式時間算法。尤其是給定了輸入x后，可以構造用p(n)步運行算法A的補算法B，其中n是x的規(guī)模，并且如果算法B試圖運行多于p(n)步，就會終止算法A。如果算法A輸出“yes”，那么算法B輸出“no”；同樣，如果算法A輸出“no”，或者算法A至少運行p(n)步而沒有產生任何輸出，那么算法B輸出“yes”。無論哪一種情況，補算法B的運行時間均為多項式時間。因此，如果表示某個判定問題的語言L在P中，那么L的補也在P中。

4．復雜類NP

復雜類NP(complexityclassNP)的定義不但包括復雜類P，還可能包括不在P中的語言。確切地說，NP類問題允許算法在P類基礎上執(zhí)行另一個操作select(b)，這個操作以非確定性的方式選擇一位(即或者為0，或者為1)，并將選擇的值賦給b。

當一個算法A中利用了select基本操作時，我們說算法A是非確定性的(non-deterministic)。如果存在輸入為x的算法A，調用select的結果，使得算法A最終輸出“yes”，則稱算法

A非確定性地接受一個串x。換句話說，就好像是我們考慮了調用select后產生的所有可能結果，而只選擇了那些導致接受的結果集(如果存在這樣一個結果集的話)，這不同于隨機選擇。復雜類NP就是那些在多項式時間內被非確定性地接受的判定問題(或者語言)L的集合，即對于輸入x∈L，存在非確定算法A及其調用select后的結果，使得在多項式時間p(n)內輸出“yes”，其中n是x的規(guī)模。注意,NP的定義并沒有強調拒絕的運行時間。對于一個在多項式時間p(n)內接受語言L的算法A，允許輸出“no”時所花費的時間比p(n)步要多。此外，由于非確定性的接受可能使得調用select過程的次數為多項式級的，因而如果一個語言L在NP中，L的補未必還在NP中。的確存在一個稱為co-NP的復雜類，包括了補在NP中的所有語言，許多研究人員認為co-NP≠NP。

5．另一種NP定義

實際上，存在另一種更直觀的復雜類NP的定義。這種NP類的定義是基于確定性的驗證，而不是非確定性的接受。我們說語言L可被一個算法A驗證(verified)，如果對于輸入串x∈L，存在另一個串y，滿足對于輸入z=x+y，算法A輸出“yes”，其中符號“+”表示連接。由于串y可幫助我們證明x的確在L中，因此稱串y為L中成員的證書(certificate)。當一個串不在L中時，我們不做驗證的聲明。驗證概念可使我們給出復雜類NP的另一種定義，即把復雜類NP定義為所有語言L的集合，這些語言L定義的判定問題可在多項式時間內得到驗證。換句話說，存在確定算法A，對于任一輸入x∈L，利用證書y在多項式時間p(n)內驗證x的確在L中，p(n)包括算法A讀其輸入z=x+y的時間，n是x的規(guī)模。這個定義蘊含著y的規(guī)模小于p(n)。正如以下定理所

表明的那樣，基于驗證的NP定義與上述描述的基于非確定性的NP定義是等價的。

定理8.2語言L可在多項式時間內確定性地被驗證，當且僅當L可在多項式時間內被非確定性地接受。

證明：首先假定語言L可在多項式時間內被確定性地驗證，即存在確定算法A(不調用選擇select過程)，對于給定多項式長度的證書y，可在多項式時間p(n)內驗證串x在L中。因此，我們可以構造以串x作為輸入的非確定性算法B，調用選擇select過程，對y中的每一位賦值。給定證書y，算法B完成串z=x+y的構造之后，調用算法A來驗證x∈L。如果存在證書y，滿足A接受z，那么顯然存在B的非確定性的選擇集合，導致B自身輸出“yes”，且B的運行時間為O(p(n))。其次，假定在多項式時間內L可被非確定性地接受，即給定L中的串x，存在運行時間為p(n)(可能包括那些select步)的非確定性算法A，對于調用這些select的某些結果序列，滿足A輸出“yes”。給定L中的串x，存在一個確定驗證算法B，用輸入為x的算法A調用過程select所產生結果的有序連接作為它的證書y，最終產生輸出“yes”。因為算法A的運行時間為p(n)，給定輸入z=x+y，所以算法B的運行時間為O(p(n))，n是x的規(guī)模。證畢。

定理8.2實際上蘊含著這兩種NP的定義是等價的，我們可以利用任何一種定義來證明一個問題在NP中。

6．P=NP的問題

計算機科學家并不能夠肯定是否P=NP。研究人員甚至不確信是否P=NP∩co-NP。大多數科學家認為P與NP和co-NP都不等，也不與它們的交集相等。事實上，在我們以下討論的NP問題的例子中，其中許多問題并不在P中。8.1.2

NP中的有趣問題

引理8.3

HAMILTIAN-CYCLE∈NP。

證明：定義非確定算法A，以圖G作為輸入，而圖G編碼為以二進制表示的鄰接表，頂點從1到N編號。首先定義A迭代調用select過程，確定1～N的N個數的序列S，然后A檢查1～N中的每個數字，確定它們只在S中出現一次，除了第一個和最后一個數字相同之外。我們驗證序列S定義了G中頂點和邊的一個回路。序列S的二進制編碼串的大小至多為n，這里n為輸入的規(guī)模。顯然，對序列S所做的兩次檢查均可在n的多項式時間內完成。下一個討論的例子是關于電路設計測試的問題。布爾電路(Booleancircuit)是一個有向圖，圖中的每個頂點稱為邏輯門(logicgate)，對應簡單的布爾函數AND、OR或NOT。邏輯門的輸入邊是它所對應布爾函數的輸入，輸出邊是它所對應布爾函數的輸出，如圖8-1所示。無輸入邊的頂點為輸入結點(inputnode)，無輸出邊的頂點為輸出結點(outputnode)。圖8-1布爾電路示例

引理8.4

CIRCUIT-SAT∈NP。

證明：我們構造一個非確定性算法在多項式時間內接受電路可滿足性問題CIRCUIT-SAT。首先，利用select過程去猜測輸入結點的值以及每個邏輯門的輸出值，然后簡單訪問電路C中的每個邏輯門g，即訪問至少有一條輸入邊的每個頂點，根據給定的g的輸入值，檢查所猜測的g的輸出值(事實上是g所對應布爾函數的正確值)。布爾函數可以是AND、OR或NOT。這個計算過程可以用多項式時間完成。如果對任一邏輯門的檢查為假，或者說所猜測的輸出值為0，那么算法輸出“no”。另一方面，如果對于每個邏輯門的檢查都成功，并輸出“1”，那么算法輸出“yes”。因此，如果確實存在C的輸入滿足指派，則存在select語句的可能結果集，使得算法在多項式時間內輸出“yes”。同樣，如果存在select語句的結果集，使得算法在多項式時間內輸出“yes”，那么必定存在C的輸入滿足指派。于是，CIRCUIT-SAT在NP中。證畢。

引理8.5

VERTEX-COVER∈NP。

證明：給定整數k和圖G,G中頂點從1至N編號。我們可以反復調用select過程，構造1～N范圍內的k個數的集合C。作為一個驗證，我們將C中的所有數插入一個字典中，然后檢查G中的每條邊，證實對于G中的每條邊(v,w)，或者v在C中，或者w在C中。如果我們找到一條邊，它的兩個端點都不在G中，那么輸出“no”。如果我們檢查了G中的所有邊，滿足每條邊都有一個頂點在C中，那么輸出“yes”。顯然，這樣的一個計算的運行時間為多項式時間。如果存在G的一個至多為k的頂點覆蓋，那么存在定義集C的一種數值指派，使得G中的每一條邊通過所做的測試，且算法輸出“yes”。同樣，如果算法輸出“yes”，那么，必定存在至多為k的頂點子集C，滿足C是G的一個頂點覆蓋。因此，VERTEX-COVER在NP中。證畢。 8.2

NP完全性

8.2.1多項式時間歸約和NP難度

我們說定義某個判定問題的語言L是多項式時間可歸約到語言M，如果存在多項式時間內的可計算函數f，它的輸入為L的輸入x，并將這個輸入轉換為M的一個輸入f(x)，使

得對于x∈L，當且僅當f(x)∈M。我們用符號 表示語言L可在多項式時間歸約到語言M。我們稱定義某個判定問題的語言M是NP難的(NP-hard)，如果NP中的其他每個語言L都可在多項式時間歸約到M。數學的形式表示為，M是NP難的，如果對于每個語言L∈NP， 。如果語言M是NP難的，且自身在復雜類NP中，那么M是NP完全(NP-complete)問題。因此，一個NP完全問題，當關注它的多項式時間的可計算性時，它是NP中最難的問題之一。如果任何人能夠證明，NP完全問題L是多項式時間可解的，那么這直接蘊含著整個NP類中的每個問題都是多項式時間可解的。在這種情況下，我們可以通過將NP類中的其他語言M歸約到語言L，然后運行語言L的算法，來接受M。換句話說，如果找到一個NP完全問題的確定性的多項式時間算法，那么，P=NP。8.2.2

Cook定理

定理8.6表明，至少存在一個NP完全問題。

定理8.6(Cook定理)電路可滿足性問題CIRCUIT-SAT是NP完全問題。

證明：引理8.4證明了CIRCUIT-SAT在NP中。因此，我們還需證明這個問題是NP難的，即要證明NP中的每個問題都可在多項式時間內歸約到CIRCUIT-SAT。考慮NP中表示某個判定問題的語言L。已知多項式規(guī)模的證書y，由于L∈NP，則對于任一x∈L，存在確定性算法D，在多項式時間p(n)內接受x，其中n是x的規(guī)模。證明的主要思想是構造一個大的、多項式規(guī)模的電路C，按照這樣一種方式模擬輸入為x的算法D，即C是可滿足的，當且僅當存在證書y，使得輸入為z=x+y的算法D輸出“yes”。任一確定算法D可用簡單計算模型，如RAM(RandomAccessMachine)實現。RAM由一個CPU和一個可尋址的存儲單元M組成。在這種情況下，存儲單元M包括輸入x、證書y和工作空間W，這些都是算法D進行計算和算法自身代碼所需要的。D的工作空間W包括臨時計算所用的寄存器和算法D執(zhí)行調用過程所需的堆棧。W的最頂層的棧結構有程序計數器(PC)，它用于識別算法D當前執(zhí)行到程序中的位置。因此CPU中沒有存儲單元。在算法執(zhí)行的每一步中，CPU讀取PC指向的下一條指令i，進行i所指示的計算，計算可以是比較、算術運算、條件跳轉、過程調用的一步等，然后更新PC，使其指到下一條要執(zhí)行的指令。因此，D的當前狀態(tài)完全由其存儲單元中的內容決定。此外，由于D在多項式時間步p(n)內接受L中的x，那么我們可以假設，它的整個有效存儲單元只由p(n)位組成，因為在p(n)步內，D至多可以訪問p(n)個存儲單元。還需注意的是，D的代碼規(guī)模是x、y，甚至W規(guī)模的常數。我們把算法D一次執(zhí)行中所需p(n)規(guī)模的存儲單元集M稱為算法D的配置(configuration)。為了模擬D的整個p(n)步，我們做S的p(n)次拷貝，使得上次拷貝的輸出作為下次拷貝的輸入，如圖8-2所示。對S第一次拷貝的輸入中，包括程序代碼D、x值、初始堆棧(連同指向D的第一條指令的PC)以及其余工作存儲單元(所有被初始化為0)的硬連線值。在第一次拷貝的輸入中，惟一未指明的真實輸入是證書y的算法D的配置單元，這些就是電路的真實輸入。同樣，除了D的一個輸出結果之外，我們忽略了對S最終拷貝的所有輸出結果，“1”代表“yes”，“0”代表“no”。電路C的總規(guī)模為O(p(n)3)，這仍然是x的多項式。圖8-2定理8.6證明圖示

8.3典型的NP完全問題

引理8.7如果 且 ，那么 。

證明:

因為 ，L1的任何實例x可在多項式時間p(n)內被轉換成L2的實例f(x)，滿足x∈L1，當且僅當f(x)∈L2，其中n是x的大小。同樣，由于 ，L2的任何實例y可在多項式時間q(m)內被轉換成L3的實例g(y)，滿足y∈L2，當且僅當g(y)∈L3，其中m是y的大小。將這兩種構造組合起來,L1的任何實例x可在時間q(k)內被轉換成L3的實例g(f(x))，滿足x∈L1，當且僅當g(f(x))∈L3，其中k是f(x)的大小。由于在p(n)步內構造了f(x)，k≤p(n)，因而q(k)≤q(p(n))。因為兩個多項式的組合總是得到另一個多項式，這個不等式蘊含著 。證畢。通常這些歸約過程具有以下三種形式：

·限制：通過說明一個已知的NP完全問題M實際上只是L的一個特例，來證明問題L是NP難的。

·局部替換：將M和L的實例劃分成一些基本單元，然后證明M的每個基本單元都可以局部地轉換為L的一個基本單元，從而將一個已知的NP完全問題M規(guī)約到L。

·分量設計：構造L實例的分量，這些分量可以執(zhí)行M實例的重要結構功能，從而將一個已知的NP完全問題M規(guī)約到L。例如，某些分量可能執(zhí)行“選擇”，而其他分量執(zhí)行函數“計算”。在圖8-3中，說明了NP完全問題是由哪個問題歸約而來的，以及在多項式歸約中使用的技術。每條有向邊表示一個多項式歸約。邊上的文字表示歸約的形式。最頂層的歸約是Cook定理。圖8-3

NP完全性證明中使用的歸約方法圖示8.3.1

CNF-SAT問題和3SAT問題

1．合取范式可滿足性問題

合取范式可滿足性(CNF-SAT)問題:取CNF中的布爾公式作為輸入，問是否存在對其布爾變量的一種指派值，使得公式的計算值為1。

容易證明，CNF-SAT在NP中，因為對于給定的布爾公式S，我們可以構造一種非確定性的算法。首先猜測S中布爾變量的一種指派值，然后依次計算S的每個子句，如果S的所有子句值都為1，那么S是可滿足的；否則S是不可滿足的。為了證明CNF-SAT是NP難的，我們在多項式時間內將電路可滿足性問題CIRCUIT-SAT歸約到這個問題。給定一布爾電路C，不失一般性,假設每個AND和OR門有兩個輸入，每個NOT門有一個輸入。為了構造與C等價的公式S，我們?yōu)檎麄€電路C的每個輸入都設置一個變量xi，并試圖將變量集限制到這些變量xi的集合上，接著將這些輸入的子表達式組合起來，構成C的公式。但是，一般而言，這種方法并不會按照多項式時間運行。因此，我們換一種方法，對C中每個門的輸出都設置一個變量yi。然后，按照下述方法構造C中每個門的公式Bg。

·如果g是一個輸入為a和b(也可以是xi或yi)、輸出為c的AND門，那么Bg=(c

(a∧b))。

·如果g是一個輸入為a和b、輸出為c的OR門，那么Bg=(c

(a∨b))。

·如果g是一個輸入為a、輸出為b的NOT門，那么Bg=(b

a)。

我們希望取所有的Bg與(AND)來構成公式S，但是這樣的公式可能不在CNF中。于是，我們首先轉換每個Bg，使其在CNF中，然后用AND運算將這些轉換過的Bg組合起來，構成CNF公式S。為了將布爾公式B轉換成合取范式CNF，構造B的真值表，如表8-1所示。表8-1布爾公式B的真值表

定理8.8

CNF-SAT問題是NP完全問題。

2．三元合取范式可滿足性問題

考慮三元合取范式可滿足性(3SAT)問題，它取布爾公式S作為輸入，公式S是一合取范式CNF，其中的每個子句只有3個文字，問S是否是可滿足的。如果一個布爾公式由AND連接的子句組成，并且每個子句由OR將文字連接而成，則該公式在CNF中。

定理8.9

3SAT問題是NP完全問題。8.3.2頂點覆蓋問題

例8.1假定圖G表示計算機網絡，圖中頂點表示路由器，邊表示物理連接。我們希望用新的昂貴的路由器替換網絡中原有的某些路由器，這些新路由器可以對發(fā)生的連接進行復雜監(jiān)控。問題是確定k個新路由器是否足夠用于監(jiān)控網絡中的每個連接，這個問題就是頂點覆蓋問題的應用實例。

通過將3SAT問題在多項式時間內歸約到頂點覆蓋問題，證明該問題是NP難的。這個歸約過程在兩個方面非常令人感興趣：一方面，它表明可將一個邏輯問題歸約到圖問題；另一方面，它舉例說明了分量設計證明技術的應用。設S是給定的3SAT問題的實例，即每個子句只有3個文字的一個CNF范式。我們構造圖G和整數k，使得G的頂點覆蓋大小至多為k，當且僅當S是可滿足的。構造過程如下：對于公式S中所用的每個變量xi，向圖G中添加兩個頂點，一個標以xi，另一個標以xi，同時向G中添加一條邊(xi,xi)。做這些標記是為了方便，在G的構造完成之后，如果G是頂點覆蓋問題的一個實例，可用整數對圖中頂點重新編號。

每條邊(xi,xi)是一個設置真值的分量，因為有這條邊在G中，頂點覆蓋必定包括至少其中的一個頂點xi或xi。此外，進行如下添加：對于S中的每個子句Ci=(a∨b∨c)，構造一個由頂點i1、i2和i3，以及邊(i1，i2)、(i2，i3)和(i3，i1)組成的三角形。注意，任何頂點覆蓋一定至少包括集合{i1，i2，i3}中的兩個頂點。每個這樣的三角形都是一個強制滿足的分量。然后對于每個子句Ci=(a∨b∨c)，通過添加邊(i1,a)、(i2,b)和(i3,c)，將這兩種類型的分量連接起來，如圖8-4所示。最終，我們設置整型參數k=n+2m，其中n，m分別是S中的變量數和子句數。因此，如果存在至多為k的頂點覆蓋，這個覆蓋的大小一定恰好等于k，這就完成了頂點覆蓋問題實例的構造。圖8-4由公式S=(x1∨x2∨x3)∧(x1∨x2∨x3)∧(x2∨x3∨x4)構造的頂點覆蓋問題實例圖

定理8.10頂點覆蓋問題是NP完全問題。

上述歸約過程說明了分量設計技術。在圖G中，我們構造設置真值的分量和滿足子句的分量，以增強子句S中的某些重要性質。

8.3.3團問題和集合覆蓋問題

類似于頂點覆蓋問題，還有一些問題也涉及從一個較大集合中選擇對象的子集，目標是優(yōu)化所選子集大小，同時滿足一個重要性質。本節(jié)我們將研究兩個這樣的問題，這就是團(clique)問題和集合覆蓋(set-cover)問題。

1．團問題

有向圖G中的一個團是頂點的一個子集C，滿足對于C中的每個頂點v和w，v≠w，(v,w)是一條邊，即對于C中每對不同頂點，存在一條邊。團問題以圖G和整數k作為輸入，問G中是否存在大小至少為k的團。

我們將證明團問題屬于NP問題留作練習。為了證明團問題是NP難的，將頂點覆蓋問題歸約到這個問題，設(G,k)是頂點覆蓋問題的一個實例。對于團問題，構造補圖GC，它和圖G有相同頂點集，但GC中存在邊(v,w)，其中v≠w，當且僅當(v,w)

G。定義團的整型參數為n－k，這里k是頂點覆蓋的整型參數。這個構造過程需要多項式時間，主要是歸約的時間，因為圖GC中存在大小至少為n－k的團，當且僅當圖G中存在大小至多為k的頂點覆蓋，如圖8-5所示。由此可得定理8.11。圖8-5證明團問題是NP難的圖例說明圖8-5(a)表明，圖G中存在大小為5的團，用灰色點表示出來。圖8-5(b)表明，圖GC中存在大小為3的頂點覆蓋，也用灰色點表示出來。

定理8.11團問題是NP完全問題。

注意，通過局部替換，問題的證明變得如此簡單。有趣的是，下一個規(guī)約也是基于局部替換技術的，甚至更簡單。

2．集合覆蓋問題

集合覆蓋問題取m個集合S1，S2，…，Sm及整數k作為輸入，問是否存在k個集合 的子集，滿足

即k個集合的并集包含原m個集合并集中的每個元素。

我們將證明集合覆蓋問題屬于NP問題留作練習。對于歸約，我們可以由頂點覆蓋問題的實例圖G和k來定義集合覆蓋問題的實例，即對于G中的每個頂點v，存在集合Sv，包

含G中依附于v的所有邊。顯然，在這些集合Sv的覆蓋中，存在一個大小為k的集合覆蓋，當且僅當G中存在大小為k的頂點覆蓋，如圖8-6所示。圖8-6證明集合覆蓋問題是NP難的圖例說明

定理8.12集合覆蓋問題是NP完全問題。

這個歸約過程說明了我們可以容易地將一個圖問題轉換成一個集合問題。下一節(jié)內容表明，我們也可以容易地將一個圖問題歸約到數問題。8.3.4子集和數問題與背包問題

1．子集和數問題

子集和數(subset-sum)問題指的是：給定n個整數的集合S及一個整數k，問集合S中是否存在子集，其和為k。以下例子可以歸結為這個問題。

例8.2假定我們有一個Internet網絡服務器，給定一個下載請求的集合。對于每個下載請求，我們可以很容易地確定請求下載文件的大小。因此，我們可以將每個網絡下載請求簡單地抽象為一個整數，即請求下載文件的大小。給定整數的集合，我們的目標是確定這些整數(請求)的一個子集，使得子集中的整數(請求下載文件大小)之和恰好等于服務器一分鐘內可容納的帶寬。這個問題就是子集和數問題的一個實例。實際上，由于它是NP完全問題，當網絡服務器帶寬和處理能力提高時，這個問題變得更難。

子集和數問題初看起來相當簡單，證明它屬于NP問題相當直接，然而它是NP完全問題。設G和k是給定頂點覆蓋問題的實例，對G中的頂點從1至n編號，邊從1至m編號，構造G的依附矩陣(incidencematrix)H，使得H［i,j］=1，當且僅當編號為j的邊依附于編號為i的頂點；否則,H［i,j］=0，如圖8-7所示。圖8-7證明子集和數問題是NP難的圖例說明我們利用H定義某些公認的大數(仍然為多項式大小)，來作為子集和數問題的輸入，即對于H中依附于頂點i的所有邊進行編碼的每一行i，我們構造數

除了上述定義的依附分量，我們還定義覆蓋邊分量，其中對于每條邊j，定義數

bj=4j

將這些數的子集設置成我們希望得到的和：

定理8.13子集和數問題是NP完全問題。

2．背包問題

下面從幾何角度看背包問題(knapsackproblem)。如圖8-8所示，給定長為s的一條線L和n個矩形集，我們可以將矩形的一個子集轉換到其底邊在L上，使得接觸L的矩形的整個區(qū)域至少為w。因此，矩形i的寬度為si，對應區(qū)域為wi。圖8-8從幾何角度看背包問題

例8.3假定我們在Internet網站上拍賣s個物品。預期的買主i希望以總價wi美元用多次抽簽方式購買物品si。如果像這樣用請求多次抽簽的方式，抽簽可能就結束不了(即買主

只想要物品si)。確定是否我們能從這次拍賣中掙得w美元導致了背包問題。(如果能夠分割，則拍賣優(yōu)化問題產生的(分數)背包問題，可以利用貪心算法予以有效解決。)

背包問題屬于NP問題，因為我們可以構造一個猜測放在子集T中物品的非確定性的多項式時間的算法，然后分別驗證它們是否滿足關于s和w的約束條件。背包問題也是NP難的，實際上子集和數問題是它的特例。特別是給定任一子集和數問題的和數的實例，都存在對應的背包問題的實例，使得每個wi=si設置為子集和數實例中的一個值，目標是大小s和價值w都等于k，其中k是子集和數問題中的和數。因此，利用限制證明技術，可得以下定理。

定理8.14背包問題是NP完全問題。8.3.5哈密爾頓回路問題和TSP問題

1．哈密爾頓回路問題

哈密爾頓回路問題是指：取圖G作為輸入，問G中是否存在簡單回路，訪問G中的每個頂點一次，并回到它的起始頂點，如圖8-9所示。圖8-9(a)給出了一個哈密爾頓回路(黑體連線部分)，圖8-9(b)給出了證明哈密爾頓回路問題是NP難的說明。引理8.3已經證明，哈密爾頓回路問題屬于NP問題，為了證明這個問題是NP完全問題，我們利用歸約的分量設計，將頂點覆蓋問題歸約到這個問題。圖8-9證明哈密爾頓回路問題是NP完全問題的圖示哈密爾頓回路只能按照圖8-10中所示的三種方式中的一種來訪問He中的結點。圖8-10在強制覆蓋He中哈密爾頓回路訪問邊的三種可能方式我們按照兩種方式，將每個強制覆蓋He中的重要頂點與H中的其他頂點連接。一種對應選擇覆蓋分量，另一種對應強制覆蓋分量。

對于選擇覆蓋分量，在X中的每個頂點到每個頂點ve,top和ve,bot之間添加一條邊，即向H中添加2kn條邊，其中n是G中頂點數。

對于強制覆蓋分量，依次考慮G中的每個頂點v，對于每個這樣的頂點v，設{e1,e2,…,ed(v)}是G中依附于v的邊的列表。利用這個列表創(chuàng)建H中的邊，連接中的頂點與中的頂點 ，i=1,2,…,d－1，如圖8-11所示。圖8-11連接強制覆蓋

定理8.15哈密爾頓回路問題是NP完全問題。

2．TSP

在旅行商問題(TravelingSalesmanProblem,TSP)中，給定圖G和一個整型參數k，且G中的每條邊被賦以一個整數成本c(e)，問G中是否存在成本至多為k的一個回路，可訪問G

中所有頂點(訪問可能多于一次)。證明TSP是NP問題也是很容易的，只需猜測頂點的一個序列，然后驗證它是否形成G中成本至多為k的回路。因為哈密爾頓回路問題是TSP問題的特例，因而證明TSP問題是NP完全問題也是容易的。也就是說，給定哈密爾頓回路問題的一個實例G，我們通過給G中的邊賦以成本c(e)=1，并設整型參數k=n，來構造TSP問題的一個實例，其中n是圖G中的頂點數。因此，利用歸約的限制形式，得到以下定理。

定理8.16

TSP問題是NP完全問題。

習題

8-1定義優(yōu)化問題LONGEST-PATH-LENGTH為無向圖G、兩個頂點以及這兩個頂點的最長簡單路徑之間的邊數上的關系。定義判定問題LONGEST-PATH={〈G,u,v,k〉：G=(V,E)是無向圖，u,v∈V，k≥0是一個整數，且G中存在從u到v的至少為k條邊的簡單路徑}，證明可用多項式時間解優(yōu)化問題LONGEST-PATH-LENGTH，當且僅當LONGEST-PATH∈P。

8-2分別利用鄰接矩陣表示法和鄰接表表示法，給出有向圖的一種二進制串的形式編碼。證明這兩種表示法是多項式相關的。

8-3

0-1背包問題的動態(tài)規(guī)劃算法是多項式時間的算法嗎？試解釋你的結論。

8-4證明一個至多常數次調用多項式時間子例程的多項式算法的運行時間為多項式時間。但是多項式次數的調用多項式時間的子例程卻可能導致指數級的算法。

8-5歸約。假設L1和L2是滿足L1<pL2的語言。對于以下每個聲明，判斷是否為真/假，并作出解釋，或者證明它是開放問題。

(1)設L1，L2∈NP。如果L1∈P，那么，L2∈P。

(2)如果L2∈P，那么，L1∈P。

(3)設L2∈NP。如果L2不是NP完全的，那么，L1也不是NP完全的。

(4)設L1，L2∈NP。如果L2<pL1，那么，L1和L2都是NP完全的。

(5)如果L1和L2都是NP完全的，那么，L2<pL1。

8-6設2SAT是CNF中可滿足的布爾公式集，其中每個子句中只有2個文字。證明2SAT∈P。盡可能使你所設計的算法有效。(提示：觀察可得x∨y

與

x→y等價，可將2SAT在多項式時間歸約到有向圖中的某個問題。)

8-7同一問題的易解性和難解性。有向哈密爾頓路徑問題闡述如下：給定有向圖G=(V,E)和兩個不同頂點u，v∈V，確定G中是否包含始點為u、終點為v的路徑，且訪問圖中的每個頂點僅有一次。

(1)證明有向哈密爾頓路徑問題是NP完全問題。(提示：考慮哈密爾頓回路問題。)

(2)設計一個求解有向無環(huán)圖的有向哈密爾頓路徑問題的多項式時間的算法。

8-8證明集合覆蓋問題是NP完全問題。集合覆蓋問題闡述如下：給定有限集U，U的子集集合S={S1，S2，…，Sm}，以及整數k，確定是否存在一個覆蓋U的勢為k的S的子集，即確定是否存在S'

S，滿足|S′|=k且 。

8-9子圖同構(subgraph-isomorphism)問題：以兩