第八章 NP完全問題.doc

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