第八章 NP完全問題.doc

207第八章 NP-完全問題第八章 NP-完全問題1 關(guān)于問題及算法的描述為了應(yīng)用算法復(fù)雜性理論，首先要對問題、問題的一般描述、計算模型、算法、算法的復(fù)雜性給出嚴格的定義。但在給出精確定義之前，我們先回顧一下有關(guān)概念的粗略解釋。所謂一個問題(problem)是指一個有待回答、通常含有幾個取值還未確定的自由變量的一個一般性提問(question)。它由兩部分構(gòu)成：一是對其關(guān)于參數(shù)的一般性描述；二是對該問題的答案所應(yīng)滿足的某些特性的說明。而一個問題的某個實例則可通過指定問題中所有參數(shù)的具體取值來得到。以下用表示某個問題，用表示其實例。旅行商問題的參數(shù)是由所需訪問城市的一個有限集合和中每對城市之間的距離所組成。它的一個解是對所給城市的一個排序 使得該排序極小化下面表達式（目標函數(shù)）的值 旅行商問題的一個實例是通過指定城市的數(shù)目，并指定每兩個城市之間的具體距離而得到的。例如：，就是旅行商問題的一個實例，這個實例的一個最優(yōu)解是排序，因為四個城市的這個排序所對應(yīng)旅行路線是所有可能環(huán)游路線中長度最小的，其長度為27。目前廣泛采用的描述問題的方法主要有兩種：一是將任一問題轉(zhuǎn)化為所謂的可行性檢驗問題(feasibility problem)；二是把問題轉(zhuǎn)化為判定問題(decision problem)。實際中幾乎所有問題都可直接或間接地轉(zhuǎn)述為判定問題。判定問題是答案只有“是”與“非”兩種可能的問題。一個判定問題可簡單地由其所有例子的集合與答案為“是”的例子所構(gòu)成的子集來刻畫。不過，為了反映實際問題所具有的特性，通常所采用的描述方法由兩部分組成。第一部分用諸如集合、圖、函數(shù)等各種描述分量來刻畫判定問題的一般性例子，以下用“例”表示這一部分；第二部分則陳述基于一般性例子所提出的一個“是非”提問，以下簡稱“問”。因此，一個具體例子屬于當(dāng)且僅當(dāng)它可通過用具有特定性質(zhì)的某些對象替代一般性例子的所有一般性描述分量而得到，而一個例子屬于當(dāng)且僅當(dāng)限定于該例子時，它對所述提問的回答為“是”。例 待訪問城市的有限集合、每對城市之間的距離以及一個界。問 在中存在一個總長不超過的、通過所有城市的旅行路線嗎？也就是說，存在的一個排序，使得 這是一個將優(yōu)化問題轉(zhuǎn)化成判定問題的例子。一般地，一個優(yōu)化問題可以看作是其所有實例的集合，而每一個實例為一個元素對，其中是可行解集，是目標函數(shù)。一個最優(yōu)化問題可以提出下述三種模式： 最優(yōu)化模式：求最優(yōu)解； 求值模式：求出最優(yōu)值； 判定模式：給定一個實例和一個整數(shù)，問是否存在一個可行解 ，使得？顯然，在求解最優(yōu)值不太困難的假設(shè)下，上述三種模式的每一種都不比前一種困難。一般而且比較現(xiàn)實的假設(shè)是：最優(yōu)值是一個整數(shù)，且這個整數(shù)或其絕對值的對數(shù)被輸入長度的一個多項式所界定。在這種情況下，用二分搜索(或叫折半搜索)技術(shù)證明，只要判定模式存在多項式時間算法，求值模式也存在多項式時間算法。所謂算法(algorithm)是指用來求解某一問題的、帶有一般性的一步一步的過程。它是用來描述可在許多計算機上實現(xiàn)任一計算流程的抽象形式，其一般性可以超越任何具體實現(xiàn)時的細節(jié)。注意，復(fù)雜性理論中對算法的定義與我們通常理解的具體算法(即用某種計算機語言編寫的、可在某一特定計算機上實現(xiàn)的計算機程序)有所不同。不過，將算法想象為某個具體的計算機程序，在許多情況下可以幫助我們理解有關(guān)概念和理論。附：一個算法的嚴格定義直到1936年才出現(xiàn)，丘奇(Alonzo Church)和圖靈(Alan Turing)分別在他們的文章中給出。丘奇使用稱為演算的記號系統(tǒng)來定義算法，圖靈用機器(圖靈機)來定義算法，后來證明兩者是等價的。此前，希爾伯特的第10問題就是要設(shè)計一個算法來測試多元多項式是否有整數(shù)根。不過他不用“算法”這個詞，而是用一句短語：“通過有限次運算就可以決定的過程”。我們這里采用圖靈的定義,即借用圖靈機計算模型來給出算法的精確定義。到目前為止，關(guān)于算法的描述大致有三種不同的程次：一是形式描述，即詳盡的寫出圖靈機的狀態(tài)、轉(zhuǎn)移函數(shù)等等，這是最底層也最詳細的描述；二是實現(xiàn)描述，使用日常語言來描述圖靈機的運行，如怎樣移動讀寫頭，怎樣在帶上存儲數(shù)據(jù)等，但是不給出狀態(tài)和轉(zhuǎn)移函數(shù)的細節(jié)；三是高層的描述，它也使用日常語言來描述算法，但是忽略實現(xiàn)的模型，這種描述不需要提及機器是怎樣管理它的帶子或讀寫頭的。稱一個算法求解一個問題，是指該算法可以應(yīng)用到的任一實例，并保證能找到該實例的一個解。一個算法的有效性可以用執(zhí)行該算法所需要的各種計算資源的量來度量。最典型也是最主要的兩個資源就是所需要的時間和內(nèi)存空間。但時間需求常常是決定某一特定算法在實際中是否真正有用和有效的決定性因素。應(yīng)該注意到，由于計算機速度和指定系統(tǒng)的不同，同一算法所需時間的多少隨著計算機的不同可能有很大差別。為使算法分析具有一般性和在實際中有用，所給時間的度量不應(yīng)該依賴于具體計算機，即是說，如果它們用不同的編程語言來描述，或在不同的計算機上運行，好的算法仍然保持為好的。另一點需要注意的是，即使同一算法和同一計算機，當(dāng)用它來求解某一問題的不同例子時，由于有關(guān)參數(shù)取值的變化，使得所運行時間也有很大差別。對于前一個問題的解決，人們提出了一些簡單但又能反映絕大多數(shù)計算機的基本運作原理的計算模型，如各種形式的圖靈(Turing)機、隨機存儲機(RAM)等，然后基于這些計算模型來研究算法。對于第二個問題的解決，人們引進了問題例子大小(size)的概念。所謂一個問題例子的大小是指為描述或表示它而需要的信息量。只要表示的合適，可望例子的大小的值應(yīng)該與求解的難易程度成正比。并稱相應(yīng)的表示法為編碼策略(encoding scheme)。事實上，作為輸入提供給計算機的對任一問題例子的描述可以看作是從某一有限字母表中選取所需的字符而構(gòu)成的有限長字符串。通常稱該字母表中的字符為碼，而由其中之字符如何組成描述問題例子的字符串的方法則稱為編碼策略。合理的編碼策略應(yīng)該具有可解碼性(decodability)和簡潔性(conciseness)。一種典型的方法就是利用所謂的結(jié)構(gòu)化字符串，通過遞歸、復(fù)合的方式來給出所考慮問題的合理編碼策略。給定一個問題，假設(shè)已經(jīng)找到描述問題一般性例子的一個合理編碼策略e，則對的任一實例，稱其依編碼策略e所得的描述相應(yīng)問題實例的字符串中所含有字符的個數(shù)為其輸入長度，并將該輸入長度的具體值作為例子的大小的正式度量。例如，若用字母表 中的字符表示旅行商問題的例子，則前面所給該問題的具體例子可以用字符串來描述，其相應(yīng)的輸入長度為32。我們說旅行商問題的這個例子的大小為32。雖然所有的判定問題均可用統(tǒng)一的術(shù)語來描述，但從數(shù)學(xué)上講還是不夠嚴密，不宜于給出算法的嚴格定義，也不利于算法復(fù)雜性研究。為了克服這些不足，我們引進“語言”這一術(shù)語，它與判定問題有著很自然的聯(lián)系。設(shè)是一個字符集，用表示由中的字符組成的所有有限長字符串的集合。的任何非空子集都稱為上的一個語言(language)。例如01,001,111,1010110就是字符集0,1上的一個語言。判定問題與語言之間的對應(yīng)關(guān)系是通過編碼策略來實現(xiàn)的。一旦選定了某個字符集，則對于任一個判定問題及其編碼策略e，和e將會把中的所有字符串劃分為三部分：那些不是的例子的編碼、那些對的回答為“非”的例子的編碼和那些對的答案為“是”的例子的編碼。后一類編碼正是與通過e來聯(lián)系的語言。定義：如果一個結(jié)論對語言成立，則說它在編碼策略e下對問題成立（計算復(fù)雜性理論所直接考慮的是對語言或字符串集的分析）。對于任何兩個合理的編碼策略e和e，問題的某個性質(zhì)要么對和均成立，要么對二者均不成立。因此，可以直接說某個性質(zhì)對成立或不成立，也常常將簡記為。但是，這樣的省略卻失去了對輸入長度的具體確定辦法，而我們還需要象這樣的一個參變量以便能確切表述復(fù)雜性的概念。為此，以后總是隱含假定：對每個判定問題，均有一個不依賴于編碼方式的函數(shù)Length：該函數(shù)的值將與從任一合理的編碼策略所得的關(guān)于的任一例子的輸入長度多項式相關(guān)。這里，多項式相關(guān)是指：對于的任一合理編碼策略e，都存在兩個多項式和，使得如果且為在e下的編碼，則有這里，表示字符串的長度。易知，的任何兩個合理的編碼策略將導(dǎo)出多項式相關(guān)的輸入長度。例如，對于旅行商問題，對應(yīng)的判定問題的任一例子，可以定義 這里，表示。在后面的陳述中，會交替地使用(判定)問題、語言這兩個術(shù)語而不加區(qū)分。2 圖靈機與確定性算法為了算法復(fù)雜性分析具有普適性，即一個算法的效能與具體的計算機無關(guān)，我們需要選定一種可用于描述計算的計算模型。第一個給出這種模型的是英國數(shù)學(xué)家圖靈，后人稱他所提出的模型為圖靈機。圖靈機本質(zhì)上是一個具有存儲載體（通常用一個有無限多個方格線性帶表示）的、按照具體指令可完成向左或右移動、放置標記、抹去標記以及在計算終止時停機等四種基本操作的、用于描述算法的語言。在原理上，與我們用于和計算機交流的更為復(fù)雜的各種程序語言同樣有力。由于其簡單性，圖靈機及其各種變形已被廣泛用于計算復(fù)雜性的理論研究。首先選擇確定性單帶圖靈機(deterministic one-tape Turing machine)，簡稱確定圖靈機，記為DTM。一個DTM由一個有限狀態(tài)控制器、一個讀寫頭和一條雙向的具有無限多個格的線性帶所組成。 有限狀態(tài)控制器 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 讀寫頭 圖8-2-1 單帶確定性圖靈機示意一個DTM程序(program)應(yīng)詳細規(guī)定下列信息：(a).帶中所用字符的一個有限集合，它應(yīng)包含輸入字符表子和一個特別的空白符號 ；(b).一個有限狀態(tài)集，它包括初始狀態(tài)和兩個特有的停機狀態(tài)。(c).一個轉(zhuǎn)移函數(shù)表示了狀態(tài)變化、字符變化及讀寫頭移動方向，而且是唯一的。一個DTM程序運行很簡單。假設(shè)對DTM的輸入為字符串，則該字符串首先被一格一個字符地存放在帶格1到帶格中。所有其它的帶格均存放空白字符。該程序從初始狀態(tài)開始它的運算，并且，讀寫頭先位于帶格1，然后按下述規(guī)則一步一步地進行：若當(dāng)前狀態(tài)為或，則計算終止，且如果，就回答“是”，否則回答“非”。若當(dāng)前狀態(tài)為，且為讀寫頭當(dāng)前掃描帶格中的字符，而轉(zhuǎn)移函數(shù)此時對應(yīng)的取值為，那么，該程序?qū)?zhí)行這樣的幾個操作：讀寫頭抹去當(dāng)前帶格中的，并寫上字符；同時，如果，則讀寫頭左移一格；如果，則讀寫頭右移一格。最后，有限狀態(tài)控制器將從狀態(tài)變到狀態(tài)。這樣就完成了程序的一步計算，并為下一步計算做好準備，除非已處于停機狀態(tài)?？梢?，當(dāng)前狀態(tài)、帶格的內(nèi)容以及讀寫頭所在的位置是圖靈機的要素，這三者的整體稱為一個格局，圖靈機的運行就是根據(jù)轉(zhuǎn)移函數(shù)發(fā)出的指令從一個格局轉(zhuǎn)移的另一個格局。有了DTM這個計算模型以及定義于它上面的程序概念，就可以給出算法及其復(fù)雜性函數(shù)的嚴格定義。設(shè)M是一個DTM程序，輸入字符表為。我們說程序M接受字符串，如果它作用于時停機于狀態(tài)，并稱為程序M所識別的語言。因此，若，則M的計算要么停機于狀態(tài)，要么永不停機（不是該問題的實例）。只有當(dāng)一個DTM程序?qū)Χx于其輸入字符表上的所有可能字符串均（在有限步內(nèi)）停機時，才稱其為一個算法（實際是判定器）。相應(yīng)地，稱一個DTM程序M在編碼策略e之下求解判定問題 ，如果M對定義于其輸入字符表上的所有輸入字符串均停機，且有 。一個DTM程序M對于輸入的計算時間定義為該程序從開始直至進入停機狀態(tài)為止所運行的步數(shù)。由此可以給出時間復(fù)雜性函數(shù)的定義：對于一個對所有輸入均停機的DTM程序M，其時間復(fù)雜性函數(shù) 定義為：若存在一個多項式，使得對所有的，有，則稱程序M為一個多項式時間DTM程序。我們稱為P語言類。如果存在一個多項式時間DTM程序，它在編碼策略e之下求解，即，則稱該判定問題屬于P。3 NP類問題不難看出，上面定義的P類語言只能用來描述那些存在有效算法（多項式時間）的問題。然而，在實際中存在許多別的重要問題，對于它們，至今尚未找到有效的求解算法。其中有一大類這樣的問題，雖然不知道求解它們的有效算法，但是，一旦通過某種辦法給出了其答案的一個猜測或估計，就能設(shè)計出一個多項式時間算法來驗證其真實性(稱為多項式時間可驗證性)。這類問題的分析和描述需要借助另一類圖靈機作為計算模型。非確定性單帶圖靈機(non-deterministic one-tape Turing machine)，簡記為NDTM，是一種假想的機器。通常有兩種方式描述它：多值模型和猜想模塊模型。多值模型認為它和確定性圖靈機的共同之處是也包括：(a).帶中字符集，使得，且 ；(b).有限狀態(tài)集；不同之處在于(c).多值轉(zhuǎn)移函數(shù), 確定性圖靈機在任一狀態(tài)下只能做一種運算，而非確定性圖靈機可以被想象為在同一時刻能夠獨立、并行地完成多種運算（表現(xiàn)在轉(zhuǎn)移函數(shù)的多值性），這顯然不現(xiàn)實。通過允許作不受限制的并行計算可以對不確定性算法做出明確的解釋。每當(dāng)要作某種選擇時，算法就好像給自己復(fù)制了若干副本，每種可能的選擇有一個副本，于是，許多副本同時被執(zhí)行。第一個獲得成功的副本將引起對其它副本計算的結(jié)束。如果一個副本獲得不成功的完成則只該副本終止。接受或拒絕確定性計算拒絕接受非確定性計算 圖8-3-1 與確定性算法的比較不確定算法舉例： 程序8-3-1 不確定性排序算法pro NSort(A,n)/對n個正整數(shù)排序integer A(n),B(n),n,i,j;B:=0 /對B進行初始化for i to n do j:=choice(1.n); if Bj0 then failure； endif; Bj:=Ai; endfor for i to n-1 do /驗證B的次序 if BiBi+1 then failure； endif; endforprint(B);success; endNSort 程序8-3-2 0/1背包判定問題的不確定算法proc NPack(P,W,n,M,R,X)integer P(n),W(n),R,X(n),n,M,i;X:=0 /對X進行初始化for i to n do Xi:=choice(0,1); endfor; if then failure; else success;endif;endNPack“猜想模塊模型”是另一種更形象、直觀的解釋方法?？蓪DTM描述成：除多了一個猜想模塊（guessing module）外，NDTM與DTM有著完全相同的結(jié)構(gòu)，而這個猜想模塊帶有自己的僅可對帶進行寫操作的猜想頭，它提供寫下猜想的方法，僅此而已。猜想模塊有限狀態(tài)控制器 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 猜想頭讀寫頭 圖8-3-2 NDTM猜想模塊模型示意圖 基于這一模型，一個NDTM程序可以類同于一個DTM程序的方式來進行定義，并用相同的記號（包括帶中字符集，輸入字符表，空白符號，狀態(tài)集，初始狀態(tài)，兩個停機狀態(tài)和，以及狀態(tài)轉(zhuǎn)移函數(shù) 但對于一個輸入，NDTM程序的計算過程卻與DTM程序的計算過程不同，它把計算過程分為兩個階段，即猜想階段、檢驗階段。第一階段為猜想階段。開始時，輸入字符串被寫在由格1到格的帶上，其余帶格為空白字符。讀寫頭將掃描帶格1，而猜想頭在掃描帶格 -1，有限狀態(tài)控制器處于不起作用狀態(tài)，猜想模塊處于起作用狀態(tài)，并一次一步地指示猜想頭：要么在被掃描的帶格中寫下中的某一個字符并左移一格；要么停止。若為停止，猜想模塊即變?yōu)椴黄鹱饔玫?，而有限狀態(tài)控制器變?yōu)槠鹱饔玫牟⑻幱跔顟B(tài)。猜想模塊是否保持起作用，以及起作用時該從中選擇哪個字符寫在帶格中，均由猜想模塊以某種完全任意的方式?jīng)Q定。當(dāng)有限狀態(tài)控制器處于狀態(tài)時，檢驗階段就開始了。從此時起，計算機就在該NDTM程序的指示下，按照與DTM程序完全相同的規(guī)則進行。而猜想模塊及其猜想頭在完成了將所猜字符串寫到帶上的任務(wù)后將不再參與到程序的執(zhí)行中去。當(dāng)然，在檢驗階段，前面所猜字符串可能會被，而且通常將被考察。當(dāng)有限狀態(tài)控制器進入到兩個停機狀態(tài)之一時，計算就會停止。若停機為，則說是一個可接受的計算，否則（包括永不停機），說是一個未接受的計算。一般說來，對于一個給定的輸入字符串，NDTM程序M將會做無限多個可能的計算，對每一個中的可能猜想串都有一個相應(yīng)的計算。如果這些計算中至少有一個為可接受的計算，則稱NDTM程序M接受，相應(yīng)地M所識別的語言為 一個NDTM程序M接受的時間定義為：在M對于的所有可接受計算中，程序從一開始直到停機狀態(tài)為止在猜想和檢驗階段所進行的步數(shù)的最小值。而M的時間復(fù)雜性函數(shù)則定義為： 若存在多項式，使得對所有的有，則稱NDTM程序M為一個多項式時間NDTM程序。并稱 為NP語言類。稱判定問題在編碼策略e下屬于NP，若。與P類語言時的討論一樣，只要編碼策略是合理的，就可以簡單地稱問題屬于NP。因為任何現(xiàn)有的計算模型都可以通過加上一個類似于NDTM中的帶有只寫頭的猜想模塊來擴充，然后相對于所得的模型重新描述上述的正式定義，而且所有如此得到的計算模型在多項式時間內(nèi)可相互轉(zhuǎn)換的意義下將是等價的。因此，也沒有必要特別提及NDTM模型，我們將簡單地說“多項式時間不確定性算法”，并將NP類語言與所有可用多項式時間不確定性算法求解的判定問題等同看待。例子：考慮無向圖的團問題：例：給定一個有個頂點的無向圖和一個整數(shù)。問：是否包含一個具有個頂點的完全子圖（團）？如果用鄰接矩陣表示圖，用二進制串表示整數(shù)，則團問題的一個實例可用長度為的二進制串表示。團問題可表示為語言 一個接受語言CLIQUE的非確定性算法可以設(shè)計如下：第一階段將輸入串進行分解，并計算出，以及用表示的整數(shù)。若輸入不具有形式或不是一個平方數(shù)，則拒絕輸入。這階段可在內(nèi)完成。第二階段，非確定性地選擇的一個元子集，并用一個位向量A1.n表示：Ai=1當(dāng)且僅當(dāng)，因而A中恰有個1.程序8-3-3 非確定性選擇算法integer j,m;j:=0;for i to n do m:=choice(0,1); case:m=0: Ai:=0; m=1; Ai:=1; j:=j+1; endcaseendforif jk then failure; endif 第三階段，確定性地檢查的團性質(zhì)。若是一個團則接受，否則拒絕。這可以在時間內(nèi)完成。因此整個算法的時間復(fù)雜性為。如果圖不包含一個團，則算法的第二階段產(chǎn)生的任何元子集不具有團性質(zhì)。因此算法沒有導(dǎo)致接受狀態(tài)的計算路徑。反之，若圖含有一個團，則算法的第二階段中有一個計算路徑產(chǎn)生，使得在算法的第三階段導(dǎo)致接受狀態(tài)。注意到，算法的第二階段是非確定性的且耗時為。整個算法的計算時間復(fù)雜性主要取決于第三階段的驗證算法，即給定圖的一個團猜測，驗證它是否是一個團。若驗證部分可在多項式時間內(nèi)完成，則整個非確定性算法具有多項式時間復(fù)雜性。這一特征具有一般性，為此我們定義驗證算法：驗證算法定義為具有兩個自變量的算法A，其中一個自變量是通常的輸入串X，另一個自變量是一個稱為“證書”的二進制串Y。如果對任意串XL，存在一個證書Y并且A可以用Y來證明XL，則算法A就驗證了語言L. 稱 為多項式時間可驗證語言類。定理1：。證明：先證明。對于任意，設(shè)是一個多項式且A是一個多項式時間驗證算法，則下面的非確定性算法接受語言：1） 對于輸入，非確定性地產(chǎn)生一個字符串；2） 當(dāng)A(X,Y)=1時接受X.該算法的第一步與團問題的第二階段非確定性算法一樣，至多在時間內(nèi)完成。第二步的計算時間是|X|和|Y|的多項式，而。因此它也是|X|的多項式。整個算法可多項式時間內(nèi)完成。至此。 反之，設(shè)，且非確定性圖靈機M在多項式時間內(nèi)接受語言。設(shè)M在任何情況下只有不超過個的下一動作選擇，則對于輸入串X，M的任一動作序列可用的長度不超過的字符串來編碼。不失一般性，設(shè)。驗證算法A(X,Y)用于驗證“Y是M上關(guān)于輸入X的一條接受計算路徑的編碼”。即當(dāng)Y是這樣一個編碼時A(X,Y)=1. A(X,Y)顯然可在多項式時間內(nèi)確定性地進行驗證，且 因此。 證畢定理2 若，則存在一個多項式，使得可以用一個時間復(fù)雜性為的確定性算法來求解。證明：設(shè)A為求解的一個多項式時間不確定性算法，其時間復(fù)雜性由一個多項式來界定。不失一般性，設(shè)可在多項式時間內(nèi)被估值。因此，對于長度為的每個被接受的輸入，必然存在字符集上長度至多為的某個猜想字符串，使算法A的檢驗階段在不多于步內(nèi)回答“是”。若，則所需要考慮的可能猜測的數(shù)目最多為。對于一個長度為的給定輸入，通過應(yīng)用算法A的確定性檢驗階段到相應(yīng)的多個可能猜測字符串中的每一個，直到停止或運行步，我們可以肯定地發(fā)現(xiàn)A對于該輸入是否有一個可接受計算。如果A在該時間界內(nèi)遇到一個導(dǎo)致可接受計算的猜測串，則該模擬過程回答“是”；否則回答“非”。這顯然形成了一個求解的確定性算法，而且該算法的時間復(fù)雜度將以為上界，其等價于。 證畢定理2的證明指出，在非確定性圖靈機上時間復(fù)雜性為的判定問題與在確定性圖靈機上時間復(fù)雜性為的問題相當(dāng)，因此，直觀上我們有理由認為多項式時間不確定性算法要比多項式時間確定性算法的速度快得多，能夠在多項式時間內(nèi)求解后者所不能夠求解的許多其它問題。由此及許多其它理由，在目前已知知識背景下，人們普遍認為P是NP的真子集。關(guān)于這方面的研究基本上有兩條線路：1） 證明NP類中的某些問題是難解的，從而得到。但是這同原問題的難度幾乎相當(dāng)，也許只有建立一套全新的數(shù)學(xué)論證方法才有希望解決。2） 考慮NP類中問題之間的關(guān)系，從中找到一些具有特定性質(zhì)的、與P中問題有顯著不同的問題。沿此路線人們已經(jīng)證明了在NP類中存在一個稱為NP完全的子類，并由此發(fā)展出一套著名的NP完全理論。而證明一個問題是NP完全的通常被認為一個告訴我們應(yīng)該放棄尋找、設(shè)計求解該問題的有效算法（多項式時間算法）的強有力證明。4 NP完全問題研究P=NP的問題有兩條基本思路： 1 證明NP類中的某些問題是難解的，從而得到NPP。但是要證明這一點幾乎同證明P=NP一樣困難。2 考察NP類中問題之間的關(guān)系，從中找到一些具有特殊性質(zhì)的問題。沿著這一路線人們已經(jīng)證明了在NP類中存在被稱為NP-完全的子類，簡稱NPC問題，并由此發(fā)展了一套著名的NP完全理論。本節(jié)簡要介紹NP-完全性理論。為此，首先引入各語言之間的多項式變換的概念。定義1 所謂從一個語言到另一個語言的多項式變換是指滿足下面兩個條件的函數(shù)，(1) 存在計算的一個多項式時間DTM程序；(2) 對于所有的有：當(dāng)且僅當(dāng)。用表示存在一個從語言到語言的多項式變換。相應(yīng)地，對于判定問題，設(shè)e1和e2是相應(yīng)的編碼策略。若，則記為。也可以從問題的角度來敘述：由判定問題到判定問題的多項式變換是滿足下列條件的函數(shù)，(1) 可由一個多項式時間的確定性算法來計算；(2) 對于所有的有：當(dāng)且僅當(dāng)。定義2 稱一個語言（判定問題）為NP-完全的（NPC），如果，且對于所有別的語言（判定問題）均有。按照定義2，要證明問題是NP完全的，需要證明所有的NP問題均能夠經(jīng)多項式變換變成。這幾乎是很難做到的。如果NP-完全問題比較多，我們也不能對每一個這樣的問題都這樣驗證。為此我們討論一些NPC問題的有用的性質(zhì)。性質(zhì)1 如果，則意味著。性質(zhì)2 如果，則。由性質(zhì)1，2，不能推出下列結(jié)論，定理 2 設(shè)是NP完全的，如果，則。定理 3 如果，則.定理3是證明NP完全問題的基礎(chǔ)。但這需要一個NPC問題作為源問題。Cook首先給出了這樣一個問題-可滿足性問題?？蓾M足性問題是數(shù)理邏輯中一個重要問題，它定義在布爾變量之上。給定布爾變量集，上的一個真值分配是指一個映射 。上的一個子句C就是由一些布爾變量（或它們的“非”）通過邏輯“或”連接起來的布爾表達式 （8.4.1）其中，。若存在對于布爾變量集的一個真值分配，使得該子句取值為真，則說該子句被滿足。子句的集合說是可滿足的，如果存在的一個真值分配，使得集合中的每個子句的取值均為真?？蓾M足性問題可陳述如下：例 給定布爾變量之集以及上子句的一個集合C。問 是否存在的一個真值分配，使得C是可滿足的。Cook定理 可滿足性問題是NP-完全問題。從Cook的開創(chuàng)性工作至今，人們已經(jīng)發(fā)現(xiàn)并證明了數(shù)千個NPC問題（如，0/1背包問題和Hamilton回路問題），總結(jié)出證明NP-完全性的幾種方法，并建立了如何分析、進而近似求解NP-完全問題的方法。以下列出幾個典型的NPC問題： 三維匹配問題3DM(3 Dimensional Matching)例： 給定三個互不相交的、均含有個元素的集合，取。問： 包含一個匹配嗎？即是說，是否存在一個子集，使得，且中任意兩個三元組都沒有相同的分量。 三元精確覆蓋問題X3C(Exact Cover by 3-sets)例：給定有限集合 ，以及的三元子集族。問：含有的一個精確覆蓋嗎？即是說，是否存在一個子族，使得的每個元素恰好只出現(xiàn)在的一個三元子集中。注意到，如果令，則三元匹配問題就轉(zhuǎn)化為三元精確覆蓋問題（若已知道三元匹配問題是NP-完全問題，那么，三元精確覆蓋問題也必是NP-問題)。 頂點覆蓋問題VC（Vertex Cover）例：給定一個圖G(V,E)和一個正整數(shù)K|V|.問： 是否存在G的一個頂點數(shù)不超過K的覆蓋？即是否存在一個頂點子集V/ V,|V/| K，使得對于每一條邊u,vE，u與v中至少有一個屬于V/. Hamilton 回路問題HC（Hamiltonian Circuit）例：已知一個圖G(V,E)。問：G含有一個Hamilton回路嗎？G的Hamilton回路是指包含圖G的所有頂點的簡單回路(圈)，即是G的頂點的一個排序：v1,v2, , vn，其中n=|V|，使得對所有的i: 1 i 3，令 最后令 要證明上述轉(zhuǎn)換的確是一個變換，只需證明： 可滿足當(dāng)且僅當(dāng)可滿足。設(shè)為滿足的一個真賦值，以下證明可擴展成滿足的一個真賦值：。因為中的變量可分解成不同的集合，而每個的變量僅出現(xiàn)在屬于的子句中，我們僅需要說明如何將擴充到各個即可，且證明在上述四種情形的每一種情形下，中的所有子句均被滿足。若屬于情形 或情形 ，則中的字句已被所滿足，從而可任意地擴展它到，如對所有的，令。若是由情形所確定的，那么為空集，而的賦值已經(jīng)使中的單個子句取真值。若是由情形所確定的，因為為的一種可滿足性真賦值，必然存在一個最小的整數(shù)，使得文字在之下被賦予真值。若為1或2，則可對，令；若為或，則對于，令；其余情況，令。 容易證明，這些選擇將保證中所有的子句均被滿足，進而中的所有子句也均被賦值所滿足。反之，若為的一個可滿足性真賦值，則不難證明對于中變量的限制必形成對的一個可滿足性真賦值。至此，我們證明了可滿足當(dāng)且僅當(dāng)可滿足。要證明上述變換可在多項式時間內(nèi)完成，只需注意到中三元子句的數(shù)目被的一個多項式所界定,因為，任一個子句的長度不超過。也就是說，3SAT例子的大小由SAT例子的大小的一個多項式函數(shù)所界定。由此，根據(jù)上述構(gòu)造方法，不難證明它是一個多項式變換。例 8.5.2 團問題（CLIQUE）例：給定一個無向圖和一個正整數(shù)。問：是否包含一個團？即是否存在，且對任意，有。可以證明CLIQUE是NP問題，下面通過3-SATCLIQUE來證明CLIQUE是NP難的，從而說明CLIQUE是NP完全的。設(shè)是一個三元合取范式，其中構(gòu)造圖如下：對于每個子句定義三個頂點：分別與子句中的成分對應(yīng)，以每個子句對應(yīng)的三個頂點為一部分，構(gòu)造一個部圖，只要而且（不是互非的），則頂點與頂點之間就連一條邊（參看圖8-5-1）。以下證明可滿足當(dāng)且僅當(dāng)有團。如果可滿足，則存在邏輯變量的一組真值分配，使得，因而每個子句都取真值：。在每個子句中至少有一個成分取真值，這樣在G的每部分中取一個頂點，這個頂點對應(yīng)的子句成分是取真值的，我們得到一個子集合。因為中任何兩個頂點屬于不同部分，而且它們所對應(yīng)的成分不可能是互為非的（因為都取真值），所以這兩個頂點是相連的。因而構(gòu)成一個團。反之，如果有一個團，則中的頂點來源于部圖G的每一部分恰好一個。對于，等于邏輯變量時，則給分配真值；如果等于邏輯變量的非，則給分配假值。這樣就給部分邏輯變量分配了值，而且這種分配不會出現(xiàn)矛盾（根據(jù)圖G的定義），其余未提到的變量隨意取定值即可。對于這種真值分配，一定是滿足的，因為每個子句中至少有一個成分取真值?？疾炖觴2x3x1x3x1x2x1x3x2 圖 8.5.1 一個三元子句對應(yīng)的圖例 8.5.3 頂點覆蓋問題VERTEX-COVER例：給定無向圖和一個正整數(shù)。問：是否有覆蓋，即是否存在，使得對任意，有。頂點覆蓋問題是NP問題。我們通過CLIQUEVERTEX-COVER來證明VERTEX-COVER是NP-完全的。對于CLIQUE，設(shè)n個頂點的圖G(V,E)有團,則的補圖有n-k覆蓋。反之亦然。例 8.5.4 精確覆蓋問題XC例：已知有限集合的子集族 問：是否包含一個精確覆蓋，即是否存在，使得中元素互不相交，且。這個問題是NPC問題。我們將利用它證明定和子集問題是NPC問題。例 8.5.5 定和子集問題DSS例：給定非負整數(shù)集合S，正整數(shù)M問：是否存在子集,使得給定精確覆蓋的一個實例：集合，其子集族，構(gòu)造定和子集問題的一個實例：，其中，其中，當(dāng)時；當(dāng)時。取。當(dāng)含有的精確覆蓋時，令，則。反之，由令可知是的精確覆蓋。例 8.5.6 劃分問題PARTS例：已知一個有限集合，及對每個賦予的權(quán)值問：是否存在一個子集，使得以下證明DSS PARTS。給定非負整數(shù)集合和正整數(shù)，構(gòu)造集合，其中當(dāng)且僅當(dāng)有一個和數(shù)為的子集時，有一劃分。例 8.5.7 0/1背包（判定）問題 0/1 KPS例：給定一個有限集合，對于每個，對應(yīng)一個值和另一個值。另外給定一個約束值和目標問：是否存在的一個子集，使得，而且以下證明：PARTS KPS。給定一個劃分問題的實例：有限集合，及對每個的一個權(quán)值。構(gòu)造一個0/1背包問題實例：，定義。再令。如果有一個劃分，則，因而，而且，取即是0/1背包問題上述實例的解。反之，若是0/1背包問題上述實例的解，則，而且，因而，于是取即得劃分問題上述實例的解。例 8.5.8 區(qū)間排序問題（Sequencing within intervals）例：給定任務(wù)的有限集合，對于每個任務(wù)，相應(yīng)有一個開始時間和終止時間以及工作時間，其中 ， 。問：是否存在任務(wù)集的一個可行時間排序表，即是否存在函數(shù)，滿足下面兩個條件：a) 對每個，有且；b) 若，則或。證明：選取劃分問題作為“參照物”：有限集合以及對每個的權(quán)值。現(xiàn)在由劃分的一般性實例構(gòu)造區(qū)間排序問題的一般性實例。令。將用一項任務(wù)來置換，并令其滿足, 。再引進一個附加任務(wù)，其滿足, 。這一構(gòu)造過程顯然可以在多項式時間內(nèi)完成。以下證明：當(dāng)且僅當(dāng)上述劃分問題的例子回答為是時所構(gòu)造的區(qū)間排序問題例子的回答才為是。附加任務(wù)對于可行時間排序表的限制表現(xiàn)在兩個方面。首先，它確保為奇數(shù)時不可能構(gòu)造出一可行排序，因為此時由，而，故不可能被排序。同時，為奇數(shù)表明所對應(yīng)的劃分問題例子的回答必為非。故以下不妨設(shè)為偶數(shù)，但這時附加任務(wù)所起的第二個限制就表現(xiàn)出來了。因為是偶數(shù)，所以，并由可行排序的第一個要求知，可行排序必然使,這樣就限制了余下的任務(wù)只能安排被任務(wù)分離的兩個時間段內(nèi)，且每個時間段的長度為，如下圖所示B/2B/2B/2+1B/2 時間 圖 8.5.2 區(qū)間排序示意圖因此，排序問題就被轉(zhuǎn)化為把余下任務(wù)劃分為兩個子集的問題，其中一個子集中所選的任務(wù)都被安排在任務(wù)之前的時間段內(nèi)完成，而另一個子集中的任務(wù)均被安排在任務(wù)之后的時間段內(nèi)完成。由于兩個時間段的總的時間長度恰好等于除了以外的所有任務(wù)總的工作時間，故兩個時間段恰好被排滿。然而要做到這一點的充要條件是存在一個子集，使得。因此，對劃分問題的回答為是當(dāng)且僅當(dāng)對相應(yīng)的區(qū)間排序問題存在一個可行時間排序，即對它的回答也為是。至此，證明了劃分問題可多項式變換到區(qū)間排序問題。例 8.5.9 有向哈密頓圈問題DHC例：給定有向圖問：G是否有一個有向Hamilton圈，即長度為，而且恰好經(jīng)過每個頂點一次，然后回到起始頂點。DHC是NP問題。我們通過CNF-可滿足性 DHC證明DHC是NP完全的。i1r設(shè)，個邏輯變量：。畫一個有行和列的數(shù)組，第行表示子句。對每個作兩個相鄰的列，前一列代表，后一列代表，。若是的成分，則在對應(yīng)行與列交叉處畫一個；若是的成分，則在對應(yīng)行與列交叉處畫一個。在和兩列之間引入兩個頂點： 在列的頂端，在列的底部。對于每個，從向上到畫兩條（由邊組成的）鏈，一條把列上的連起來，另一條把列的連起來。然后再畫邊，。在每一行的右端引一個方框 i ,并畫邊(ur, i)和(i,v1)，再畫邊( i,i+ ),。如下圖C1C2C3C41234u1u4u3u2u5v1v4v3v2v5x1x4x3x2x5x1x4x3x2x5圖 8.5.3 Hamilton 問題此外，還要將圖中的每一個用如下左邊的子圖替代， i用如下右邊的子圖替代(見圖4.3)。這里，Ai是入口頂點，Bi是出口頂點，每條邊( i ,i+ )代之以（Bi，Ai+1）,邊(ur,i )和( i,v1)分別代之以(ur, A1 )和(Br ,v1).而 RisRi s+1表示從Ris進入 的w1頂點，Ri s1 從 的w3頂點引出。至此，有向圖構(gòu)造完畢(見圖8.5.3)。若滿足，S是相應(yīng)的真值分配。則的有向Hamilton圈可以從v1開始，行進到u1，然后到v2，再u2，v3，再u3，ur.在由vi向上行進到ui時，若xi在S中為真則采用xi對應(yīng)那一列；否則沿xi對應(yīng)的列向上行進。這個圈將從ur行進到A1，然后經(jīng)過R1 1，R1 2，R1 p ，B1(注意，這里的R1,1實際上應(yīng)該是R1,j+1 ，而j是第一個進到的 ，然后諸R1,k按照逆時針循環(huán)檢查)到A2，最后回到v1。在任一子圖 的Ris行進到Ri s1的過程中，當(dāng)且僅當(dāng)某個子圖 的頂點還不在v1到Ris的路徑上時，則轉(zhuǎn)移到第i行的 子圖。注意到，若的長度是ip，則 至多轉(zhuǎn)移到ip-1個 子圖，這是因為在至少已經(jīng)通過了一個 子圖。從而，若滿足，則有一個有向Hamilton圈。i反之，若有一個有向Hamilton圈，則的有向Hamilton圈上的頂點v1開始，由于子圖和子圖 的結(jié)構(gòu)，這樣的有向圈必須向上恰好沿每一對(xi，xi)中一列行進。另外，圈的這部分在每一行必須至少經(jīng)過一個子圖。因此，用于從vi行進到ui（i=1,2, ,n）的那一列定義了一組使為真的真值分配。AiBiRi1Ri3Ri2Ri4Ripw22w32w12圖 8.5.4 Hamilton圈分解圖r i 例 8.5.10 三元精確覆蓋問題X3C例：給定有限集合X,|X|=3q,以及X的三元子集族C。問： C含有X的一個精確覆蓋嗎？即是否存在一個子族，使得X的每個元素恰好只出現(xiàn)的一個三元子集中。這個問題是NPC問題。我們將利用它證明Steiner樹問題是NPC問題。該問題可廣泛用于描述諸如有關(guān)服務(wù)設(shè)施、廠址的最優(yōu)設(shè)置、某個區(qū)域內(nèi)最廉價交通網(wǎng)、通訊線路的設(shè)計等實際問題。例 8.5.11 Steiner樹問題例：給定圖，對其每條邊都有相應(yīng)的權(quán)，另外有G的頂點子集，某個界。問：是否存在G的一顆子樹，使，而且？以下證明Steiner樹問題是NPC。選X3C問題作為參照物：，三元子集族，構(gòu)造Steiner樹問題的相應(yīng)例子如下：取，其中，。CiqCi2Ci1v0x1x2x3x3qC/X 圖 8.5.5 Steiner樹問題令所有邊的權(quán)值為1，。顯然這一構(gòu)造過程可在多項式時間內(nèi)完成。如果為的一個精確覆蓋，則取，其中 ， 由于每個恰好出現(xiàn)在的某個三元子集里，故是連通的無圈圖。而且，因而是一棵樹。注意到,且，由此知Steiner樹問題的回答為“是”。反之，若為的一棵Steiner樹，則每個都是的頂點。不妨設(shè)每個都是的葉頂點，因為，否則的話，頂點的度數(shù)大于1，及存在邊，刪去其中一條邊，如。由于，不可能都屬于，否則包含有圈，將不屬于的那條邊添入得到另一棵樹，已知是總權(quán)值不變的Steiner樹。再由連通性，每個恰好和某個在中鄰接，令 ，則顯然是的一個精確覆蓋。至此，證明了X3C問題可多項式變換到Steiner樹問題。 6 NP困難問題設(shè)和是兩個判定問題，我們說在多項式時間內(nèi)可圖靈歸約為，記做，如果存在的一個算法，它多次調(diào)用求解的算法作為其子程序，而且，若假設(shè)每次調(diào)用該子程序均需用單位時間，則為一個多項式時間算法。稱為從到的多項式歸約。圖靈歸約也有多項式變換類似的兩個性質(zhì)，特別地，如果判定問題可以歸約到，則至少和一樣難。圖靈歸約的定義可不限于判定問題，它可以適用于最優(yōu)化問題等更廣的一類問題。定義8.6.1 對于問題，如果存在一個NP完全問題，使得，則稱問題是NP困難的（NP-hard）.由定義8.6.1， 所有