第九講-NP完全問題-算法設計與分析課件

AlgorithmsDesignTechniquesandAnalysis第10章NP完全問題——ComputabilityTheoryAlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis本章內(nèi)容IntroductionofaclassofproblemsforwhichnoefficientalgorithmshavebeenfoundP類NP類NP完全問題co-NP類NPI類AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis10.1引言設∏是任意問題，如果對問題∏存在一個算法，它的時間復雜性是O(nk)，其中∏是輸入大小，k是非負整數(shù)，我們說存在著求解問題n的多項式時間算法。這類算法在可以接受的時間內(nèi)實現(xiàn)問題求解，e.g.,排序、串匹配、矩陣相乘。但是，現(xiàn)實世界中的許多有趣問題并不屬于這個范疇，因為求解這些問題所需要的時間量要用指數(shù)和超指數(shù)函數(shù)(如2n和n!）來測度。隨著問題規(guī)模的增長而快速增長。在計算機科學界已達成這樣的共識，認為存在多項式時間算法的問題是易求解的，而對于那些不大可能存在多項式時間算法的問題是難解的。AlgorithmsDesignTechniquesa易解問題與難解問題的主要區(qū)別

在學術界已達成這樣的共識：把多項式時間復雜性作為易解問題與難解問題的分界線，主要原因有：1)多項式函數(shù)與指數(shù)函數(shù)的增長率有本質(zhì)差別問題規(guī)模n多項式函數(shù)指數(shù)函數(shù)lognnnlognn2n32nn!1010.01121103.31033.2100100010243628800204.32086.4400800010483762.4E18505.650282.225001250001.0E153.0E641006.6100664.41000010000001.3E309.3E157AlgorithmsDesignTechniquesandAnalysis易解問題與難解問題的主要區(qū)別在學術界已達成這樣的2)計算機性能的提高對易解問題與難解問題算法的影響

假設求解同一個問題有5個算法A1~A5，時間復雜度T(n)如下表，假定計算機C2的速度是計算機C1的10倍。下表給出了在相同時間內(nèi)不同算法能處理的問題規(guī)模情況：

T(n)nn′變化n′/n10n100010000n′=10n1020n5005000n′=10n105nlogn2501842n<n′<10n7.372n270223n3.162n1316n′=n+log10≈n+3≈1AlgorithmsDesignTechniquesandAnalysis2)計算機性能的提高對易解問題與難解問題算法的影響T(n)3)多項式時間復雜性忽略了系數(shù)，不影響易解問題與難解問題的劃分問題規(guī)模n多項式函數(shù)指數(shù)函數(shù)n8108nn10001.1n20.01n53906255×108510001.6111.035101081091010002.5941.0721001016101010200013780.621000102410111030002.47×10411024觀察結論：n≤100時，（不自然的）多項式函數(shù)值大于指數(shù)函數(shù)值，但n充分大時，指數(shù)函數(shù)仍然超過多項式函數(shù)。AlgorithmsDesignTechniquesandAnalysis3)多項式時間復雜性忽略了系數(shù)，不影響易解問題與難解問題的AlgorithmsDesignTechniquesandAnalysis難解問題這一類含有許許多多問題，其中還包含了數(shù)百個著名的問題，它們有一個共同的特性，即如果它們中的一個是多項式可解的，那么所有其他的問題也是多項式可解的。此外，現(xiàn)存的求解這些問題的算法的運行時間，對于中等大小的輸入也要用幾百或幾千年來測度。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis判定問題和最優(yōu)化問題判定問題:在研究NP完全性理論時，我們很容易重述一個問題使它的解只有兩個結論:yes或no，在這種情況下，稱問題為判定問題。最優(yōu)化問題:

與此相對照，最優(yōu)化問題是關心某個量的最大化或最小化的問題。在前面的章節(jié)中，已經(jīng)遇到過大量的最優(yōu)化問題，像找出一張表中的最大或最小元素的問題，在有向圖中尋找最短路徑間題和計算一個無向圖的最小生成樹的問題。如果我們有一個求解判定問題的有效算法，那么很容易把它變成求解與它相對應的最優(yōu)化問題的算法。反之亦然。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis例子10.1

設S是一個實數(shù)序列，ELEMENTUNIQUENESS問題為，是否S中的所有的數(shù)都是不同的。判定問題:ELEMENTUNIQUENESS.輸入:一個整數(shù)序列S問題:在S中存在兩個相等的元素嗎?最優(yōu)問題:ELEMENTCOUNT輸入:一個整數(shù)序列S輸出:一個在S中頻度最高的元素。這個問題可以用顯而易見的方法在最優(yōu)的時間O(nlogn)解決，這意味著它是易解的。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis例子10.2

給出一個無向圖G=(V,E)，用k種顏色對G著色是這樣的問題:對于V中的每一個頂點用k種顏色中的一種對它著色，使圖中沒有兩個鄰接頂點有相同的顏色。這個問題是難解的.AlgorithmsDesignTechniquesa例子10.2COLORING問題（圖著色問題）輸入:(著色數(shù))k,(節(jié)點數(shù))5,(圖的邊)(1,2)(1,4)...寫出長度為n(節(jié)點數(shù))的字符串,例如,RGRBG,RGRB,RBYGO,RGRBY,R%*$@等，至少有kn個不同著色情況。找到符合要求（任何兩個鄰接頂點顏色不同）的最小的k值31245例子10.2COLORING問題（圖著色問題）輸入:AlgorithmsDesignTechniquesandAnalysis例子10.2(Continue)判定問題:COLORING輸入:一個無向圖G=(V,E)和一個正整數(shù)k1。問題:G可以k著色嗎?即G最少可以用k種顏色著色嗎?這個問題的一個最優(yōu)形式是，對一個圖著色，使圖中沒有兩個鄰接的頂點有相同的顏色，所需要的最少顏色數(shù)是多少?這個數(shù)記為χ(G)，稱為G的色數(shù)。最優(yōu)化問題:

CHROMATICNUMBER輸入：一個無向圖G=(V,E)。輸出：G的色數(shù)。AlgorithmsDesignTechniquesa四色猜想

地圖四色定理(Fourcolortheorem)最先是由一位叫古德里（FrancisGuthrie）的英國大學生提出來的。

四色問題的內(nèi)容是：“任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色?！?/p>

AlgorithmsDesignTechniquesandAnalysis四色猜想地圖四色定理(Fourcolortheore四色猜想

1852年，剛從倫敦大學畢業(yè)的FrancisGuthrie提出了四色猜想。1878年著名的英國數(shù)學家Cayley向數(shù)學界征求解答。此后數(shù)學家Heawood

花費了畢生的精力致力于四色研究，于1890年證明了五色定理（每個平面圖都是5頂點可著色的）。直到1976年6月，美國數(shù)學家K.Appel與W.Haken，在3臺不同的電子計算機上，用了1200小時，作了100億判斷，才終于完成了“四色猜想”的計算機證明。

AlgorithmsDesignTechniquesandAnalysis四色猜想1852年，剛從倫敦大學畢業(yè)的FrancisGuAlgorithmsDesignTechniquesandAnalysis例子10.3

給出一個無向圖G=(V,E)，對于某個正整數(shù)k,G中大小為k的團集，是指G中有k個頂點的一個完全子圖。團集問題是問一個無向圖是否包含一個預定大小的團集。判定問題:CLIQUE.輸入:一個無向圖G=(V,E)和一個正整數(shù)k。問題:G有大小為k的團集嗎?最優(yōu)化問題:MAX-CLIQUE.輸入：一個無向圖G=(V,E).輸出:一個正整數(shù)k，它是G中最大團集的大小AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis

如果我們有一個求解判定問題的有效算法，那么很容易把它變成求解與它相對應的最優(yōu)化問題的算法。例如，我們有一個求解圖著色判定問題的算法A，則可以用二分搜索并且把算法A作為子程序來找出圖G的色數(shù)。很清楚，1<=x(G)<=n，這里n是G中頂點數(shù)，因此僅用O(1ogn)次調(diào)用算法A就可以找到G的色數(shù)。由于我們正處理多項式時間的算法，logn因子是不重要的。因為這個理由，在NP完全問題的研究中，甚至在一般意義上的計算復雜性或可計算性的研究中，把注意力限制在判定問題上會比較容易一些AlgorithmsDesignTechniquesa10.2P類

因此，易解問題和難解問題的劃分標準可基于對所謂判定問題的求解方式。事實上，實際應用中的大部分問題問題可以很容易轉(zhuǎn)化為相應的判定問題，如：

排序問題

給定一個實數(shù)數(shù)組，是否可以按非降序排列?圖著色問題：給定無向連通圖G=(V,E)，求最小色數(shù)k，使得任意相鄰頂點具有不同的著色

給定無向連通圖G=(V,E)和正整數(shù)k，是否可以用k種顏色.....?AlgorithmsDesignTechniquesandAnalysis10.2P類因此，易解問題和難解問題的劃分標準可基AlgorithmsDesignTechniquesandAnalysis10.2P類

定義10.1設A是求解問題∏的一個算法，如果在展示問題∏的一個實例時，在整個執(zhí)行過程中，每一步都只有一種選擇，則稱A是確定性算法。因此如果對于同樣的輸入，實例一遍又一遍地執(zhí)行，它的輸出從不改變。特點：對同一輸入實例，運行算法A，所得結果是一樣的。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis10.2P類定義10.2判定問題的P類由這樣的判定問題組成，它們的yes/no解可以用確定性算法在運行多項式步數(shù)內(nèi)，例如在O(nk)步內(nèi)得到，其中k是某個非負整數(shù)，n是輸入大小。也就是說：如果對于某個判定問題∏，存在一個非負整數(shù)k，對于輸入規(guī)模為n的實例，能夠以O(nk)的時間運行一個確定性算法，得到y(tǒng)es或no的答案，則稱該判定問題∏是一個P(Polynomial)類問題。事實上，所有易解問題都是P類問題。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysisP類的問題排序問題：給出一個n個整數(shù)的表，它們是否按非降序排列?不相交集問題：給出兩個整數(shù)集合，它們的交集是否為空?最短路徑問題：給出一個邊上有正權的有向圖G=(V,E)，兩個特異的頂點s,t∈V和一個正整數(shù)k，在s到t間是否存在一條路徑，它的長度最多是k。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysisP類的問題2著色問題:給出一個無向圖G，它是否是2可著色的?即它的頂點是否可僅用兩種顏色著色，使兩個鄰接頂點不會分配相同的顏色?注意，當且僅當G是二分圖，即當且僅當它不包含奇數(shù)長的回路時，它是2可著色的。2可滿足問題:給出一個合取范式(CNF)形式的布爾表達式f，這里每個子句恰好由兩個文字組成，問f是可滿足的嗎？AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis如果對于任意問題C，∏的補也在C中，我們說問題類∏

∈C在補運算下是封閉的。例如，2著色問題的補可以陳述如下:給出一個圖G，它是不2可著色的嗎?我們稱這個問題為NOT-2-COLOR問題。它是屬于P的。

定理10.1

P類問題在補運算下是封閉的。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis10.3NP類NP類由這樣的問題∏組成，對于這些問題存在一個確定性算法A，該算法在對∏的一個實例展示一個斷言解時，它能在多項式時間內(nèi)驗證解的正確性。即如果斷言解導致答案是yes，就存在一種方法可以在多項式時間內(nèi)驗證這個解。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis不確定性算法對于輸入x，一個不確定性算法由下列兩個階段組成:猜測階段驗證階段p177AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis猜測階段在這個階段產(chǎn)生一個任意字符串y，它可能對應于輸入實例的一個解，也可以不對應解。事實上，它甚至可能不是所求解的合適形式，它可能在不確定性算法的不同次運行中不同。它僅僅要求在多項式步數(shù)內(nèi)產(chǎn)生這個串，即在O(ni)時間內(nèi)，這里n=|x|，i是非負整數(shù)。對于許多問題，這一階段可以在線性時間內(nèi)完成。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis驗證階段在這個階段，一個不確定性算法驗證兩件事首先，它檢查產(chǎn)生的解串y是否有合適的形式，如果不是，則算法停下并回答no;另一方面，如果y是合適形式，那么算法繼續(xù)檢查它是否是問題實例x的解，如果它確實是實例x的解，那么它停下并且回答yes，否則它停下并回答no。我們也要求這個階段在多項式步數(shù)內(nèi)完成，即在O(nj)時間內(nèi)，這里j是一個非負整數(shù)。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis設A是問題∏的一個不確定性算法，我們說A接受問題∏的實例I，當且僅當對于輸入I存在一個導致yes回答的猜測。換句話說，A接受I當且僅當可能在算法的某次執(zhí)行上它的驗證階段將回答yes。要強調(diào)的是，如果算法回答no，那么這并不意味著A不接受它的輸人，因為算法可能猜測了一個不正確解。AlgorithmsDesignTechniquesa定義(不確定性算法):設A是求解問題∏的一個算法，如果算法A以如下猜測+驗證的方式工作，稱算法A為不確定性(nondeterminism)算法：猜測階段：對問題的輸入實例產(chǎn)生一個任意字串y，在算法的每次運行，y可能不同，因此猜測是以不確定的形式工作。這個工作一般可以在線性時間內(nèi)完成。驗證階段：在這個階段，用一個確定性算法驗證兩件事：首先驗證猜測的y是否是合適的形式，若不是，則算法停下并回答no；若是合適形式，則繼續(xù)檢查它是否是問題x的解，如果確實是x的解，則停下并回答yes，否則停下并回答no。要求驗證階段在多項式時間內(nèi)完成。

不確定性算法與NP類問題AlgorithmsDesignTechniquesandAnalysis定義(不確定性算法):設A是求解問題∏的一個算法，如果算法A注意對不確定性算法輸出yes/no的理解：若輸出no，并不意味著不存在一個滿足要求的解，因為猜測可能不正確；若輸出yes，則意味著對于該判定問題的某一輸入實例，至少存在一個滿足要求的解。AlgorithmsDesignTechniquesandAnalysis注意對不確定性算法輸出yes/no的理解：Algorithm不確定的算法:偽代碼VoidnondetA(Stringinput)

Strings=genCertif();

booleancheckOK=verifyA(input,s)

if(checkOK)Output“yes“

returnchecOK為false時不作反應.不確定的算法:偽代碼VoidnondetA(StringAlgorithmsDesignTechniquesandAnalysisNP類至于一個(不確定性)算法的運行時間，它僅僅是兩個運行時間的和：一個是猜測階段的時間，另一個是驗證階段的時間。因此它是O(ni)+O(nj)=O(nk)，k是某個非負整數(shù)。定義10.3判定問題類NP由這樣的判定問題組成:對于它們存在著多項式時間內(nèi)運行的不確定性算法。AlgorithmsDesignTechniquesa南京理工大學NP類問題定義(NP類問題):如果對于判定問題∏，存在一個非負整數(shù)k，對于輸入規(guī)模為n的實例，能夠以O(nk)的時間運行一個不確定性算法，得到y(tǒng)es/no的答案，則該判斷問題∏是一個NP(nondeterministicpolynomial)類問題。

※注意：NP類問題是對于判定問題定義的，事實上，可以在多項式時間內(nèi)應用非確定性算法解決的所有問題都屬于NP類問題。

南京理工大學NP類問題定義(NP類問題):如果對于判定問題例子（圖著色問題）Input:(著色數(shù))k,(節(jié)點數(shù))5,(圖的邊)(1,2)(1,4)...Guessing指寫出長度為n(節(jié)點數(shù))的字符串,例如,RGRBG,RGRB,RBYGO,RGRBY,R%*$@等.至少有kn個“guessings”。Checking指檢查一guessed字符串是否合法及是否是一個k-著色。如果寫字符串的時間是O(p1(n)),checking時間是O(p2(n));而且p1(n),p2(n)是n的多項式(從而也是輸入長度的多項式),則該不確定算法有多項式時間。如果輸入的圖能k著色則不確定算法停機并給出yes回答。31245例子（圖著色問題）Input:(著色數(shù))k,(節(jié)點數(shù))AlgorithmsDesignTechniquesandAnalysis例子考慮問題COLORING，我們用兩種方法證明這個問題屬于NP類。方法1:設I是COLORING問題的一個實例，s被宣稱為I的解。容易建立一個確定性算法來驗證，是否確實是I的解。從NP類的非形式定義可得COLORING問題屬于NP類。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis方法2建立不確定性算法當圖G用編碼表示后，一個算法A可以很容易地構建并運作如下首先通過片頂點集合產(chǎn)生一個任意的顏色指派以“猜測”一個解First。接著，A驗證這個指派是否是有效的指派，如果它是一個有效的指派，那么A停下并且回答yes，否則它停下并回答no。請注意，根據(jù)不確定性算法的定義，僅當對問題的實例回答是yes時，A回答yes。其次是關于需要的運行時間，A在猜測和驗證兩個階段總共花費不多于多項式時間。AlgorithmsDesignTechniquesa關于P與NP關系的初步思考--從字面含義1)若問題∏屬于P類，則存在一個多項式時間的確定性算法，對它進行判定或求解；顯然，也可以構造一個多項式時間的非確定性算法，來驗證解的正確性，因此，問題也屬NP類。因此，顯然有

PNP2)若問題∏屬于NP類，則存在一個多項式時間的非確定性算法，來猜測并驗證它的解；但不一定能構造一個多項式時間的確定性算法，來對它進行求解或判定。

因此，人們猜測P≠NP，但是否成立，至今未得到證明。P=NP?是計算機科學中最大的問題之一AlgorithmsDesignTechniquesandAnalysis關于P與NP關系的初步思考--從字面含義1)AlgorithmsDesignTechniquesandAnalysis10.4NP完全問題術語“NP完全”表示NP判定問題的一個子類，它們在下述意義上是最難的，即如果它們中的一個被證明用多項式時間確定性算法可解，那么NP中的所有問題用多項式時間確定性算法可解，即NP=P。NP完全問題是NP類問題的子類，一個具有特殊性質(zhì)與特殊意義的子類。

AlgorithmsDesignTechniquesa歸約(Reduction)人們普遍認為，P=NP不成立多數(shù)人相信，存在至少一個不可能有多項式級復雜度的算法的NP問題——這就是NP完全問題。Reduction(“約化”或“歸約”)：一個問題A可以約化為問題B的含義即是，可以用解決問題B的解法來解決問題A，或者說，問題A可以“變成”問題B。如：一元一次方程可以“歸約”為一元二次方程。求解一個一元一次方程和求解一個一元二次方程。那么我們說，前者可以約化為后者，意即知道如何解一個一元二次方程那么一定能解出一元一次方程。我們可以寫出兩個程序分別對應兩個問題，那么我們能找到一個“規(guī)則”，按照這個規(guī)則把解一元一次方程程序的輸入數(shù)據(jù)變一下，用在解一元二次方程的程序上，兩個程序總能得到一樣的結果。這個規(guī)則即是：兩個方程的對應項系數(shù)不變，一元二次方程的二次項系數(shù)為0。按照這個規(guī)則把前一個問題轉(zhuǎn)換成后一個問題，兩個問題就等價了。AlgorithmsDesignTechniquesandAnalysis歸約(Reduction)人們普遍認為，P=NP不成立AlgorithmsDesignTechniquesandAnalysis歸約(Reduction)問題A可“歸約”為問題B直觀意義：B的時間復雜度高于或者等于A的時間復雜度。也就是說，問題A不比問題B難。

很顯然，歸約具有一項重要的性質(zhì)：歸約具有傳遞性。如果問題A可約化為問題B，問題B可約化為問題C，則問題A一定可約化為問題C。定義10.4:P178AlgorithmsDesignTechniquesaNP完全問題NP完全問題是一類具備如下特殊性質(zhì)的NP類問題∏（該問題本身）就是一個NP類問題每一個NP類問題都可以通過多項式時間歸約化到∏NP類問題NP完全問題AlgorithmsDesignTechniquesandAnalysisNP完全問題NP完全問題是一類具備如下特殊性質(zhì)的NP類問題NNP完全問題的定義定義9.7(NP完全問題):令∏是一個判定問題，如果問題∏屬于NP類問題，并且對NP類問題中的每一個問題∏′，都有∏′∝poly∏，則稱判定問題∏是一個NP完全問題(NPcompleteproblem,NPC)。NP類問題NP完全問題AlgorithmsDesignTechniquesandAnalysisNP完全問題的定義定義9.7(NP完全問題):令∏是一個判對“NP完全問題”的評述NP完全問題是NP類問題中最難的一類問題，至今已經(jīng)發(fā)現(xiàn)了幾千個，但一個也沒有找到多項式時間算法。如果某一個NP完全問題能在多項式時間內(nèi)解決，則每一個NP完全問題都能在多項式時間內(nèi)解決。這些問題也許存在多項式時間算法，因為計算機科學是相對新生的科學，肯定還有新的算法設計技術有待發(fā)現(xiàn)；這些問題也許不存在多項式時間算法，但目前缺乏足夠的依據(jù)來證明這一點。AlgorithmsDesignTechniquesandAnalysis對“NP完全問題”的評述NP完全問題是NP類問題中最難的AlP類問題、NP類問題、NP完全問題的關系NP完全問題NP類問題P類問題AlgorithmsDesignTechniquesandAnalysisP類問題、NP類問題、NP完全問題的關系NP完全問題NP類問NP困難問題

難解問題中還有一類問題，雖然也能證明所有的NP類問題可以在多項式時間內(nèi)變換到問題∏，但并不能證明∏也是NP類問題，所以∏不是NP完全的。但問題∏至少與任意NP類問題有同樣的難度，這樣的問題稱為NP困難問題。NP類問題NP難問題AlgorithmsDesignTechniquesandAnalysisNP困難問題難解問題中還有一類問題，雖然也能證明所有AlgorithmsDesignTechniquesandAnalysisNP-困難的

與NP-完全的

定義10.5一個判定問題稱為是NP困難的，如果對于NP中的每一個問題’，

存在’poly。定義10.6一個判定問題稱為是NP完全的，如果下列兩個條件同時成立。(1)在NP中，(2)對于NP中的每一個問題’，’poly。NP完全問題和NP困難問題’間的差別是：必須是NP類的而’可能不在NP中。AlgorithmsDesignTechniquesa10.4.1可滿足性問題可滿足性問題即合取范式的可滿足性問題，來源于許多實際的邏輯推理的應用。合取范式形如A1A2...An，其中子句Ai(1≤i≤n)形如：a1a2...ak,其中aj稱為文字，為布爾變量或它的否定。一個子句是文字的析取。SAT問題是指：是否存在一組對所有布爾變量的賦值，使得整個合取范式為真?例如當x1和x3都為真、其余文字任意賦值時，f值為真。AlgorithmsDesignTechniquesandAnalysis10.4.1可滿足性問題可滿足性問題即合取范式的可滿足性問AlgorithmsDesignTechniquesandAnalysis可滿足性問題判定問題:SATISFIABILITY.輸入:一個合取范式的布爾公式f。問題:f是可滿足的嗎?

定理10.2SATISFIABILITY問題是NP完全的實際上，可滿足性問題被證明是NP完全的第一個問題。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis10.4.1可滿足性問題可滿足性（英語：Satisfiability）問題又叫布林可滿足性問題（Booleansatisfiabilityproblem；簡寫SAT）屬于判定問題，它是歷史上第一個被證明NP完全問題。1971年，美國的Cook證明了Cook定理：布爾表達式的可滿足性(SAT)問題是NP完全的。

AlgorithmsDesignTechniquesa為了證明SATISFIABILITY是NP完全的，必須證明對NP中的任意問題，有poly

SATISFIABILITY。假設的實例I的規(guī)模是n，在p(n)的判定時間里最多有cp(n)個動作，因此可以用cp(n)時間時間構造布爾表達式f，也就是說poly

SATISFIABILITY這就是著名的Cook定理為了證明SATISFIABILITY是NP完全的，必須證明對對于一個確定的邏輯電路，是否存在一種輸入使得輸出為true，是第一個被證明的NPC問題。其它的NPC問題都是由這個問題約化而來的。我們知道，一個邏輯電路由若干個輸入，一個輸出，若干“邏輯門”和密密麻麻的線組成，如下圖：直觀描述這是個較簡單的邏輯電路，當輸入1、輸入2、輸入3分別為True、True、False或False、True、False時，輸出為True。AlgorithmsDesignTechniquesandAnalysis對于一個確定的邏輯電路，是否存在一種輸入使得輸出為true，直觀描述有輸出無論如何都不可能為True的邏輯電路嗎？

AlgorithmsDesignTechniquesandAnalysis這個邏輯電路中，無論輸入是什么，輸出都是False。因此，這個邏輯電路不存在使輸出為True的一組輸入。直觀描述有輸出無論如何都不可能為True的邏輯電路嗎？AlNP完全問題（補充）邏輯電路問題(可滿足性問題)屬于NPC問題。這是有嚴格證明的。它顯然屬于NP問題，并且可以直接證明所有的NP問題都可以約化到它。約化證明過程相當復雜，其大概意思是說任意一個NP問題的輸入和輸出都可以轉(zhuǎn)換成邏輯電路的輸入和輸出（想想計算機內(nèi)部也不過是一些

0和1的運算），因此對于一個NP問題來說，問題轉(zhuǎn)化為了求出滿足結果為True的一個輸入（即一個可行解）。AlgorithmsDesignTechniquesandAnalysisNP完全問題（補充）邏輯電路問題(可滿足性問題)屬于NPCNP完全問題（補充）第一個NP完全問題（Cook定理1971）可滿足性問題是NP完全問題1972年，Karp證明了十幾個問題都是NP完全的。3SAT，3DM，VC，團，HC，劃分更多的NP完全問題1979年：300多個1998年：2000多個這些NP完全問題的證明思想和技巧，以及利用他們證明的幾千個NP完全問題，極大地豐富了NP完全理論。NP完全問題（補充）第一個NP完全問題（Cook定理1AlgorithmsDesignTechniquesandAnalysis定理10.3（歸約關系的傳遞性）設∏，∏和∏”是三個判定問題，有

poly’和’poly”，那么

poly”P179推論10.1（NP完全性的傳遞性）如果∏和∏’是NP中的兩個問題，若有’poly

，并且∏’是NP完全的，則∏是NP完全的。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis根據(jù)上面的推論，為了證明一個問題∏是NP完全的，僅需要證明以下兩個條件同時成立(1)NP；(2)存在著一個NP完全問題∏’，使’poly。例子10.5p179AlgorithmsDesignTechniquesaNP完全性的傳遞性舉例已知哈密頓回路問題是一個NP完全問題，證明貨郎擔問題也是一個NP完全問題哈密頓回路問題：給定無向圖G=(V,E)，是否存在一條回路，使得圖中每個頂點在回路中出現(xiàn)且只出現(xiàn)一次旅行商問題：給定n個城市和它們的距離矩陣，以及距離L，是否存在從某個城市出發(fā)，經(jīng)過每個城市一次且僅一次，最后回到出發(fā)城市且距離小于或等于L的路線后面是具體說明：NP完全性的傳遞性舉例已知哈密頓回路問題是一個NP完全問題，對于哈密頓回路問題中的無向圖G=(V,E)

，可以用多項式時間構造新的無向圖G=(V,E)

，使得V=V，E=E。對于E中的每條邊(u,v)賦予如下權值：通過上述轉(zhuǎn)換，轉(zhuǎn)換為旅行商問題可以證明兩個問題等價：（1）G中包含一條哈密爾頓回路，則這條路徑上的邊共有n條，每條邊長度是1，則G中存在一條路徑經(jīng)過每個頂點且一次，并且長度不超過n（2）如果G中存在一條滿足旅行商問題的路徑，則這條路徑經(jīng)過G中各個頂點一次，且僅一次，最后回到出發(fā)頂點，它肯定是一條哈密爾頓回路對于哈密頓回路問題中的無向圖G=(V,E)，可以用多南京理工大學如何證明一個問題是NP完全的？根據(jù)NP完全問題的定義（滿足的兩個性質(zhì)），顯然地，證明需要分兩個步驟進行：證明問題∏是NP類問題；即可以在多項式時間內(nèi)以確定性算法驗證一個任意生成的串，以確定它是否為問題的一個解。證明NP類問題中的每一個問題都能在多項式時間內(nèi)變換為問題∏。由于多項式問題變換具有傳遞性，所以，只需證明一個已知的NP完全問題能夠在多項式時間內(nèi)變換為問題∏.NP類問題已知的NP完全問題要證明的??問題南京理工大學如何證明一個問題是NP完全的？根據(jù)NP完全問題的AlgorithmsDesignTechniquesandAnalysis10.4.2頂點覆蓋、獨立集和團集問題頂點覆蓋:給出一個無向圖G=(V,E)和一個正整數(shù)k，是否存在大小為k的子集CV,使E中的每條邊至少和C中的一個頂點關聯(lián)?獨立集:獨立集:給出一個無向圖G=(V,E)和一個正整數(shù)k，是否存在k個頂點的子集SV，使得對于每一對頂點u，w∈S,(u,w)E?團集:團集:給出一個無向圖G=(V,E)和一個正整數(shù)k，G包含一個大小為k的團集嗎?(注意一個G中大小為k的團集是G中k個頂點的一個完全子圖。)容易證明所有這三個問題確實是NP的。AlgorithmsDesignTechniquesa南京理工大學證明最大團集問題是NP完全的下面證明團問題屬于NP完全問題，證明分兩步：1)團集問題屬于NP類問題顯然，驗證圖G的一個子圖是否構成團只需要多項式時間，所以團問題屬于NP類問題。2)可滿足性問題∝poly團集問題南京理工大學證明最大團集問題是NP完全的AlgorithmsDesignTechniquesandAnalysis可滿足性poly團集問題給出一個有m個子句和n個布爾變元x1,x2,..,xn的可滿足性實例f=C1C2…Cm，我們構造一個圖G=(V,E)，其中V是2n個文字的所有出現(xiàn)的集合(注意一個文字是一個布爾變元或它的否定)，并且E={(xi,xj)|xi和xj位于兩個不同的子句，并且xi~xj}

xyyxyzzxAlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis引理10.1f是可滿足的當且僅當G有一個大小為m的團集。

證明:一個大小為m的團集對應于一個m個不同子句中對m個文字的真指派。在兩個文字a和b間的邊意味著當a和b同時指派真值時沒有矛盾。這就得到f是可滿足的當且僅當存在著一個對于m個不同子句中的m個文字的真指派，當且僅當G有一個大小為m的團集。AlgorithmsDesignTechniquesa可滿足性∝poly團集問題對于任意一個合取范式，按照如下方式構造相應的圖G：例如

圖G的每個頂點對應于f中的每個文字，多次出現(xiàn)的重復表示；若圖G中兩個頂點對應的文字不互補，且不出現(xiàn)在同一子句中，則將其連線。（a-b連線意味著a和b同時為真）AlgorithmsDesignTechniquesandAnalysis可滿足性∝poly團集問題對于任意一個合取范式，按照如下方式設f有n個子句，則：f可滿足

n個子句同時為真每個子句至少1個文字為真G中有n個頂點之間彼此相連G中有n個頂點的團顯然，上述構造圖G的方法可在多項式時間內(nèi)完成，故有：SAT∝poly團問題。由以上證明可知，團問題是NP完全問題。SAT問題∝poly團問題同時為真，則相連AlgorithmsDesignTechniquesandAnalysis設f有n個子句，則：f可滿足SAT問題∝poly團問題同時為AlgorithmsDesignTechniquesandAnalysis可滿足性poly頂點覆蓋給出一個可滿足性實例I，我們把它變換為頂點覆蓋的一個實例I’，設I是一個有m個子句和n個布爾變元x1,x2,..,xn的可滿足性實例公式f=C1C2…Cm，構造I’如下。對于f中的每一個布爾變元xi，G包含一對頂點xi和~xi

，它們有一條邊相連;對于每個子句Cj包含的nj個文字，G包含一個大小為nj的團集Cj

；對于在Cj中的每個頂點w，有一條邊連接w到(1)中構造的頂點對(xi,~xi)中它相應的文字。這些邊稱為連通邊;令AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis引理10.2f是可滿足的當且僅當構造的圖有一個大小為k的頂點覆蓋。證明:P181AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis引理10.3設G=(V,E)是連通無向圖，那么SV是一個獨立集當且僅當V-S是G的一個頂點覆蓋。

證明設e=(u,v)是G中的任意邊，S是一個獨立集當且僅當u或v至少有一個在V-S中，即V-S是G中的頂點覆蓋。頂點覆蓋poly獨立集AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis定理10.4頂點覆蓋、獨立集和團集問題是NP完全的。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis更多NP完全問題P182AlgorithmsDesignTechniquesaco-NP類由它們的補屬于NP類的那些問題組成。例如：旅行商問題的補：給出n個城市和它們之間的距離，不存在長度為k或更少的任何旅程，情況是那樣嗎?可滿足性問題(SAT)的補：給出一個公式f，不存在使得f為真的布爾變量指派，是嗎?換言之，f是不可滿足的嗎?換個角度來看，co-NP類問題也是NP完全問題。10.5co-NP類AlgorithmsDesignTechniquesandAnalysisco-NP類由它們的補屬于NP類的那些問題組成。例如：10.AlgorithmsDesignTechniquesandAnalysis10.5co-NP類co-NP類由它們的補屬于NP類的那些問題組成。定義10.7問題對于co-NP類是完全的，如果(1)

在co-NP中(2)對于co-NP中的每一個問題’，’polyco-NP類問題co-NP完全問題AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysisco-NP類定理10.5問題∏是NP完全的，當且僅當它的補

對于類co-NP是完全的。定理10.6重言式問題:給出一個DNF公式f，它是重言式嗎?這個問題對于co-NP類是完全的由此得出下列結論:重言式問題屬于P當且僅當co-NP=P,重言式問題屬于NP當且僅當co-NP=NP

。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis10.6NPI類

定理10.7如果問題∏和它的補

是NP完全的，那么co-NP=NP。換句話說，如果問題∏和它的補都是NP完全的，那么NP類在補運算下是封閉的。NPIclass:theclassofproblemsthattheyandtheircomplementationareinNP,butarenotNP-complete.AlgorithmsDesignTechniquesa10.6NPI類NP類問題中還有一些問題，人們不知道是屬于P類還是屬于NP完全問題，還有待于證明其歸屬。這些問題是NP完全問題的可能性非常小，也因為不相信他們在P中，我們?nèi)藶榈卦黾恿硪粏栴}類來接納這類問題，這個類稱為NPI(NP-Intermediate)類。NP完全問題NP類問題P類問題??AlgorithmsDesignTechniquesandAnalysis10.6NPI類NP類問題中還有一些問題，人們不知道是屬于關于NPI類問題的評述NPI類是一個人為定義的、動態(tài)的概念，隨著人們對問題研究的深入，許多NPI類問題逐漸被明白無誤地證明他們原本屬于P類問題或NP完全問題。例如：線性規(guī)劃問題、素數(shù)判定問題等，在二者沒有被證明他們均屬于P類問題之前，人們一直將他們歸于NPI類問題。

AlgorithmsDesignTechniquesandAnalysis關于NPI類問題的評述NPI類是一個人為定義的、動態(tài)的概念，南京理工大學一個例子線性規(guī)劃問題設A∈Rm×n,x∈Rn,b∈Rm，在滿足Ax=b，x≥0約束下，使目標函數(shù)cTx達到最大值，其中c∈Rn.長期以來，線性規(guī)劃問題沒有多項式時間解法，也無法證明它是NP完全問題。直到20世紀80年代，這個問題得到解決，發(fā)現(xiàn)了多項式時間算法。NP完全問題線性規(guī)劃問題P類問題??南京理工大學一個例子線性規(guī)劃問題NP完全問題線性規(guī)劃問題P類南京理工大學另一個例子素數(shù)判定問題給一個整數(shù)，判定其是素數(shù)還是合數(shù)。經(jīng)過一個重要的理論突破，印度M.Agrawal教授和他的學生N.Kayal和N.Saxena于2002年宣布發(fā)現(xiàn)一個多項式時間算法。(PRIMESisinP,AnnalsofMathematics,160(2004),781–793)

NP完全問題素數(shù)判定問題P類問題??南京理工大學另一個例子素數(shù)判定問題NP完全問題素數(shù)判定問題PAlgorithmsDesignTechniquesandAnalysis10.7四種類之間的關系P184co-NP-completeNP-completeCo-NPNPIPNPAlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysisAlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis第10章NP完全問題——ComputabilityTheoryAlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis本章內(nèi)容IntroductionofaclassofproblemsforwhichnoefficientalgorithmshavebeenfoundP類NP類NP完全問題co-NP類NPI類AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis10.1引言設∏是任意問題，如果對問題∏存在一個算法，它的時間復雜性是O(nk)，其中∏是輸入大小，k是非負整數(shù)，我們說存在著求解問題n的多項式時間算法。這類算法在可以接受的時間內(nèi)實現(xiàn)問題求解，e.g.,排序、串匹配、矩陣相乘。但是，現(xiàn)實世界中的許多有趣問題并不屬于這個范疇，因為求解這些問題所需要的時間量要用指數(shù)和超指數(shù)函數(shù)(如2n和n!）來測度。隨著問題規(guī)模的增長而快速增長。在計算機科學界已達成這樣的共識，認為存在多項式時間算法的問題是易求解的，而對于那些不大可能存在多項式時間算法的問題是難解的。AlgorithmsDesignTechniquesa易解問題與難解問題的主要區(qū)別

在學術界已達成這樣的共識：把多項式時間復雜性作為易解問題與難解問題的分界線，主要原因有：1)多項式函數(shù)與指數(shù)函數(shù)的增長率有本質(zhì)差別問題規(guī)模n多項式函數(shù)指數(shù)函數(shù)lognnnlognn2n32nn!1010.01121103.31033.2100100010243628800204.32086.4400800010483762.4E18505.650282.225001250001.0E153.0E641006.6100664.41000010000001.3E309.3E157AlgorithmsDesignTechniquesandAnalysis易解問題與難解問題的主要區(qū)別在學術界已達成這樣的2)計算機性能的提高對易解問題與難解問題算法的影響

假設求解同一個問題有5個算法A1~A5，時間復雜度T(n)如下表，假定計算機C2的速度是計算機C1的10倍。下表給出了在相同時間內(nèi)不同算法能處理的問題規(guī)模情況：

T(n)nn′變化n′/n10n100010000n′=10n1020n5005000n′=10n105nlogn2501842n<n′<10n7.372n270223n3.162n1316n′=n+log10≈n+3≈1AlgorithmsDesignTechniquesandAnalysis2)計算機性能的提高對易解問題與難解問題算法的影響T(n)3)多項式時間復雜性忽略了系數(shù)，不影響易解問題與難解問題的劃分問題規(guī)模n多項式函數(shù)指數(shù)函數(shù)n8108nn10001.1n20.01n53906255×108510001.6111.035101081091010002.5941.0721001016101010200013780.621000102410111030002.47×10411024觀察結論：n≤100時，（不自然的）多項式函數(shù)值大于指數(shù)函數(shù)值，但n充分大時，指數(shù)函數(shù)仍然超過多項式函數(shù)。AlgorithmsDesignTechniquesandAnalysis3)多項式時間復雜性忽略了系數(shù)，不影響易解問題與難解問題的AlgorithmsDesignTechniquesandAnalysis難解問題這一類含有許許多多問題，其中還包含了數(shù)百個著名的問題，它們有一個共同的特性，即如果它們中的一個是多項式可解的，那么所有其他的問題也是多項式可解的。此外，現(xiàn)存的求解這些問題的算法的運行時間，對于中等大小的輸入也要用幾百或幾千年來測度。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis判定問題和最優(yōu)化問題判定問題:在研究NP完全性理論時，我們很容易重述一個問題使它的解只有兩個結論:yes或no，在這種情況下，稱問題為判定問題。最優(yōu)化問題:

與此相對照，最優(yōu)化問題是關心某個量的最大化或最小化的問題。在前面的章節(jié)中，已經(jīng)遇到過大量的最優(yōu)化問題，像找出一張表中的最大或最小元素的問題，在有向圖中尋找最短路徑間題和計算一個無向圖的最小生成樹的問題。如果我們有一個求解判定問題的有效算法，那么很容易把它變成求解與它相對應的最優(yōu)化問題的算法。反之亦然。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis例子10.1

設S是一個實數(shù)序列，ELEMENTUNIQUENESS問題為，是否S中的所有的數(shù)都是不同的。判定問題:ELEMENTUNIQUENESS.輸入:一個整數(shù)序列S問題:在S中存在兩個相等的元素嗎?最優(yōu)問題:ELEMENTCOUNT輸入:一個整數(shù)序列S輸出:一個在S中頻度最高的元素。這個問題可以用顯而易見的方法在最優(yōu)的時間O(nlogn)解決，這意味著它是易解的。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis例子10.2

給出一個無向圖G=(V,E)，用k種顏色對G著色是這樣的問題:對于V中的每一個頂點用k種顏色中的一種對它著色，使圖中沒有兩個鄰接頂點有相同的顏色。這個問題是難解的.AlgorithmsDesignTechniquesa例子10.2COLORING問題（圖著色問題）輸入:(著色數(shù))k,(節(jié)點數(shù))5,(圖的邊)(1,2)(1,4)...寫出長度為n(節(jié)點數(shù))的字符串,例如,RGRBG,RGRB,RBYGO,RGRBY,R%*$@等，至少有kn個不同著色情況。找到符合要求（任何兩個鄰接頂點顏色不同）的最小的k值31245例子10.2COLORING問題（圖著色問題）輸入:AlgorithmsDesignTechniquesandAnalysis例子10.2(Continue)判定問題:COLORING輸入:一個無向圖G=(V,E)和一個正整數(shù)k1。問題:G可以k著色嗎?即G最少可以用k種顏色著色嗎?這個問題的一個最優(yōu)形式是，對一個圖著色，使圖中沒有兩個鄰接的頂點有相同的顏色，所需要的最少顏色數(shù)是多少?這個數(shù)記為χ(G)，稱為G的色數(shù)。最優(yōu)化問題:

CHROMATICNUMBER輸入：一個無向圖G=(V,E)。輸出：G的色數(shù)。AlgorithmsDesignTechniquesa四色猜想

地圖四色定理(Fourcolortheorem)最先是由一位叫古德里（FrancisGuthrie）的英國大學生提出來的。

四色問題的內(nèi)容是：“任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色?！?/p>

AlgorithmsDesignTechniquesandAnalysis四色猜想地圖四色定理(Fourcolortheore四色猜想

1852年，剛從倫敦大學畢業(yè)的FrancisGuthrie提出了四色猜想。1878年著名的英國數(shù)學家Cayley向數(shù)學界征求解答。此后數(shù)學家Heawood

花費了畢生的精力致力于四色研究，于1890年證明了五色定理（每個平面圖都是5頂點可著色的）。直到1976年6月，美國數(shù)學家K.Appel與W.Haken，在3臺不同的電子計算機上，用了1200小時，作了100億判斷，才終于完成了“四色猜想”的計算機證明。

AlgorithmsDesignTechniquesandAnalysis四色猜想1852年，剛從倫敦大學畢業(yè)的FrancisGuAlgorithmsDesignTechniquesandAnalysis例子10.3

給出一個無向圖G=(V,E)，對于某個正整數(shù)k,G中大小為k的團集，是指G中有k個頂點的一個完全子圖。團集問題是問一個無向圖是否包含一個預定大小的團集。判定問題:CLIQUE.輸入:一個無向圖G=(V,E)和一個正整數(shù)k。問題:G有大小為k的團集嗎?最優(yōu)化問題:MAX-CLIQUE.輸入：一個無向圖G=(V,E).輸出:一個正整數(shù)k，它是G中最大團集的大小AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis

如果我們有一個求解判定問題的有效算法，那么很容易把它變成求解與它相對應的最優(yōu)化問題的算法。例如，我們有一個求解圖著色判定問題的算法A，則可以用二分搜索并且把算法A作為子程序來找出圖G的色數(shù)。很清楚，1<=x(G)<=n，這里n是G中頂點數(shù)，因此僅用O(1ogn)次調(diào)用算法A就可以找到G的色數(shù)。由于我們正處理多項式時間的算法，logn因子是不重要的。因為這個理由，在NP完全問題的研究中，甚至在一般意義上的計算復雜性或可計算性的研究中，把注意力限制在判定問題上會比較容易一些AlgorithmsDesignTechniquesa10.2P類

因此，易解問題和難解問題的劃分標準可基于對所謂判定問題的求解方式。事實上，實際應用中的大部分問題問題可以很容易轉(zhuǎn)化為相應的判定問題，如：

排序問題

給定一個實數(shù)數(shù)組，是否可以按非降序排列?圖著色問題：給定無向連通圖G=(V,E)，求最小色數(shù)k，使得任意相鄰頂點具有不同的著色

給定無向連通圖G=(V,E)和正整數(shù)k，是否可以用k種顏色.....?AlgorithmsDesignTechniquesandAnalysis10.2P類因此，易解問題和難解問題的劃分標準可基AlgorithmsDesignTechniquesandAnalysis10.2P類

定義10.1設A是求解問題∏的一個算法，如果在展示問題∏的一個實例時，在整個執(zhí)行過程中，每一步都只有一種選擇，則稱A是確定性算法。因此如果對于同樣的輸入，實例一遍又一遍地執(zhí)行，它的輸出從不改變。特點：對同一輸入實例，運行算法A，所得結果是一樣的。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis10.2P類定義10.2判定問題的P類由這樣的判定問題組成，它們的yes/no解可以用確定性算法在運行多項式步數(shù)內(nèi)，例如在O(nk)步內(nèi)得到，其中k是某個非負整數(shù)，n是輸入大小。也就是說：如果對于某個判定問題∏，存在一個非負整數(shù)k，對于輸入規(guī)模為n的實例，能夠以O(nk)的時間運行一個確定性算法，得到y(tǒng)es或no的答案，則稱該判定問題∏是一個P(Polynomial)類問題。事實上，所有易解問題都是P類問題。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysisP類的問題排序問題：給出一個n個整數(shù)的表，它們是否按非降序排列?不相交集問題：給出兩個整數(shù)集合，它們的交集是否為空?最短路徑問題：給出一個邊上有正權的有向圖G=(V,E)，兩個特異的頂點s,t∈V和一個正整數(shù)k，在s到t間是否存在一條路徑，它的長度最多是k。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysisP類的問題2著色問題:給出一個無向圖G，它是否是2可著色的?即它的頂點是否可僅用兩種顏色著色，使兩個鄰接頂點不會分配相同的顏色?注意，當且僅當G是二分圖，即當且僅當它不包含奇數(shù)長的回路時，它是2可著色的。2可滿足問題:給出一個合取范式(CNF)形式的布爾表達式f，這里每個子句恰好由兩個文字組成，問f是可滿足的嗎？AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis如果對于任意問題C，∏的補也在C中，我們說問題類∏

∈C在補運算下是封閉的。例如，2著色問題的補可以陳述如下:給出一個圖G，它是不2可著色的嗎?我們稱這個問題為NOT-2-COLOR問題。它是屬于P的。

定理10.1

P類問題在補運算下是封閉的。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis10.3NP類NP類由這樣的問題∏組成，對于這些問題存在一個確定性算法A，該算法在對∏的一個實例展示一個斷言解時，它能在多項式時間內(nèi)驗證解的正確性。即如果斷言解導致答案是yes，就存在一種方法可以在多項式時間內(nèi)驗證這個解。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis不確定性算法對于輸入x，一個不確定性算法由下列兩個階段組成:猜測階段驗證階段p177AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis猜測階段在這個階段產(chǎn)生一個任意字符串y，它可能對應于輸入實例的一個解，也可以不對應解。事實上，它甚至可能不是所求解的合適形式，它可能在不確定性算法的不同次運行中不同。它僅僅要求在多項式步數(shù)內(nèi)產(chǎn)生這個串，即在O(ni)時間內(nèi)，這里n=|x|，i是非負整數(shù)。對于許多問題，這一階段可以在線性時間內(nèi)完成。AlgorithmsDesignTechniquesaAlgorithmsDesignTechniquesandAnalysis驗證階段在這個階段，一個不確定性算法驗證兩件事首先，它檢查產(chǎn)生的解串y是否有合適的形式，如果不是，則算法停下并回答no;另一方面，如果y是合適形式，那么算法繼續(xù)檢查它是否是問題實例x的解，如果它確實是實例x的解，那么它停下并且回答yes，否則它停下并回答no。我們也要求這個階段在多項式步數(shù)內(nèi)完成，即在O(nj)時間內(nèi)，這里j是一個非負整數(shù)。