一、nP-問題的基本概念
本章的內容包括了在算法研究方面的最重要的基本理論。這些基本理論對于計算機科學
家、電氣工程師和從事運籌學等方面的工作者都是十分有用的。因此，凡是在這些領域里的工作者建議讀本章的內容。
不過，在閱讀本章之前，讀者應熟悉以下基本概念：一是算法的事先分析計算時間，它是在所給定的不同數據集下，通過研究算法中語句．的執行頻率而得到的，二是算法時間復雜度的數量級以及它們的漸近表示。如果一個算法在輸入量為n的情況下計算時間為t(n)，則記作t(n)＝o(f(n))，它表示時間以函數f(n)為上界。t(n)= (g(n))表示時間以函數g(n)為下界。這些概念在第一章都作過詳細的闡述。
另一個重要概念是關于兩類問題的區別，其中第一類的求解只需多項式時間的算法，而第二類的求解則需要非多項式時間的算法(即，g(n)大于任何多項式)。對于已遇到和作過研究的許多問題，可按求解它們的最好算法所用計算時間分為兩類。第一類問題的求解只需低次多項式時間。例如本書前面講過的有序檢索的計算時間為o(1ogn)，分類為o(nlogn)，矩陣乘法為o( )等。第二類問題則包括那些迄今已知的最好算法所需時間為非多項式時間的問題。例如貨郎擔問題和背包問題的時間復雜度分別為o( )和o( )。對于第二類問題，人們一直在尋求更有效的算法，但至今還沒有誰開發出一個具有多項式時間復雜度的算法。指出這一點是十分重要的，因為算法的時間復雜度一旦大于多項式時間(典型的時間復雜度是指數時間)，算法的執行時間就會隨n的增大面急劇增加，以致即使是中等規模的問題也不能解出。
本章所討論的nP-完全性理論，對于第二類問題，既不能給出使其獲得多項式時間的方法，也不說明這樣的算法不存在。取而代之的是證明了許多尚不知其有多項式時間算法的問題在計算上是相關的。實際上，我們建立了分別叫做nP-難度的和nP-完全的兩類問題。一個nP-完全的問題具有如下性質：它可以在多項式時間內求解，當且僅當所有其它的nP-完全問題也可在多項式時間內求解。假如有朝一日某個nP-難度的問題可以被一個多項式時間的算法求解，那末所有的nP—完全問題就都可以在多項式時間內求解。下面將會看到，一切nP-完全的問題都是nP-難度的問題，但一切nP-難度的問題并不都是nP-完全的。
二、不確定的算法
到目前為止在已用過的算法中，每種運算的結果都是唯一確定的，這樣的算法叫做確定的算法(deterministic algorithm)。這種算法和在計算機上執行程序的方式是一致的。從理論的角度看，對于每種運算的結果“唯一確定”這一限制可以取消。即可以允許算法每種運算的結果不是唯一確定的，而是受限于某個特定的可能性集合。執行這些運算的機器可以根據稍后定義的終止條件選擇可能性集合中的一個作為結果。這就引出了所謂不確定的算法 (nondeterministic algorithm)。為了詳細說明這種算法，在sParks中引進一個新函數和兩條新語句：
choice (s)…任意選取集合s中的一個元素。
failure…發出不成功完成的信號。
success…發出成功完成的信號。
賦值語句xßchoice (1：n)使x內的結果是區域[1，n]中的任一整數(沒有規則限定這種選擇是如何作出的)。failure和success的信號用來定義此算法的一種計算，這兩條語句等價于stop語句，但不能起return語句的作用。每當有一組選擇導致成功的完成時，總作出這樣的一組選擇并使算法成功地終止。當且僅當不存在任何一組選擇會導致成功的信號，那末不確定的算法不成功地終止。choice，success和failure的計算時間取為o (1)。能按這種方式執行不確定算法的機器稱為不確定機(nondeterministic machine)。然而這里所定義的不確定機實際上是不存在的，因此通過直覺可以感到這類問題不可能用“快速的”確定算法求解。
三、本節實例
[例]：（檢索）考察在給定的元素集a(1：n)中，n≥1，檢索元素x的檢索問題。應確定下標j，使得a(j)＝x，或者當x不在a中時有j＝0。此問題的一個不確定算法為
jßchoice (1：n)
if a(j)=x then print(j)；success endif
print (‘0’)；failure
由上述定義的不確定算法當且僅當不存在一個j使得a(j)＝x時輸出“0”。此算法有不確定的復雜度o(1)。
注意：由于a是無序的，因此確定的檢索算法的復雜度為 (n)。
[例]：(分類) 設a(i)，1≤i≤n，是一個尚未分類的正整數集。不確定的算法nsort(a，n)將這些數按非降次序分類并輸出。為方便起見，采用一輔助數組b(1：n)。第1行將b初始化為零。在第2~6行的循環中，每個a(i)的值都賦給b中的某個位置，第3行不確定地定出這個位置，第4行弄清b(j)是否還沒用過。因此b中整數的次序是a中初始次序的某種排列。第7~9行驗證b是否已按非降次序分類。當且僅當整數以非降次序輸出時，算法成功地完成。由于第3行對于這種輸出次序總存在一組選擇，因此算法nsort是一個分類算法，它的復雜度為o(n)。回憶前面講過的各種確定的分類算法可知它們的復雜度應為 (nlogn)。
[算法]：不確定的分類算法 [動畫]
procedure nsort(a，n)
／／對n個正整數分類／／
integer a(n)，b(n)，n，i，j
1 bß0／／b初始化為零／／
2 for iß1 to n do
3 ißchoice (1：n)
4 if b(j) 0 then failure endif
5 b(j)ßa(i)
6 repeat
7 for iß1 to n-1 do／／驗證b的次序／／
8 if b(i)>b(i+1) then failure endif
9 repeat
10 print(b)
11 success
12 end nsort
通過允許作不受限制的并行計算可以對不確定的算法作出確定的解釋。每當要作某種選擇時，算法就好像給自己復制了若干副本，每種可能的選擇有一個副本，于是許多副本同時被執行。第一個獲得成功完成的副本，將引起其它所有副本的計算終止。如果一個副本獲得不成功的完成則只該副本終止。前面說過success和failure信號相當于確定算法中的stop語句，但它們不能用來取代return語句。上述解釋是為了便于讀者理解不確定算法。
注意： 對一臺不確定機來說，當算法每次作某種選擇時，它實際上是什么副本都不作的，只是在每次作某種選擇時，具有從可選集合中選擇出一個“正確的”元素的能力(如果這樣的元素存在的話)。一個“正確的”元素是相對于導致一成功終止的最短選擇序列而定義的。在不存在導致成功終止的選擇序列的情況下，則假定算法是在一個單位時間內終止并且輸出“計算不成功”。只要有成功終止的可能，一臺不確定機就會以最短的選擇序列導致成功的終止。因為這種不確定機本來就是虛構和假想的，所以沒有必要去注意機器在每一步是如何作出正確選擇的。
完全有可能構造出一些這樣的不確定算法，它們的多種不同的選擇序列都會導致成功的完成。例8．2的過程nsort就是這樣的一個算法。如果整數a（i）有許多是相同的，那末在一個分類序列中將出現許多不同的排列。如果不是按已分好類的次序輸出這些a（i），而是輸出所用的排列，那末這樣的輸出將不是唯一確定的。今后只關心那些產生唯一輸出的不確定算法，特別是只研究那些不確定的判定算法(nondeteministic decision algorithm)。這些算法只產生“0”或“1”作為輸出，即作二值決策，前者當且僅當沒有一種選擇序列可導致一個成功的完成，后者當且僅當一個成功的完成被產生。輸出語句隱含于success和failure之中。在判定算法中不允許有明顯的輸出語句。顯然，早先對不確定計算的定義意味著一個判定算法的輸出由輸入參數和算法本身的規范唯一地確定。
雖然上面所述的判定算法的概念看來似乎限制過嚴，但事實上許多最優化問題都可以改寫成判定問題并使其具有如下性質；該判定問題可以在多項式時間內求解，當且僅當與它相應的最優化問題可以在多項式時間內求解。從另一方面說，如果判定問題不能在多項式時間內求解，那末與它相應的最優化問題也不能在多項式時間內求解。
[例]： (最大集團) 圖g＝(v，e)的最大完全子圖叫作g的一個集團(clique)。集團的大小用所含的結點數來量度。最大集團問題即為確定g內最大集團的大小問題。與之對應的判定問題是，對于某個給定的k，確定g是否有一個大小至少為k的集團。令dcliq—ue(g，k)是此集團判定問題的一個確定的判定算法。假設g的結點數為n，g內最大集團的大小可在多次應用dclique(g，k)而求得。對于每個k，k=n，n一1，n一2，…直到dcliclue輸出l為止，過程dclique都要被引用一次。如果dclique的時間復雜度為（b)，則最大集團的大小可在n，f(n)時間內求出二假如最大集團的大小可以在g(n)時間內確定，于是其判定問題也可在g(n)時間內解出。因此最大集團問題可在多項式時間內求解，當且僅當集團的判定問題可在多項式時間內求解。
[例]： (0／1背包) 背包的判定問題是確定對 ，1≤i≤n，是否存在一組o／1的賦值，使得 ≥r和 ≤m。r是一個給定的數，而這些 及 都是非負的數。顯然，如果背包的判定問題不能在確定的多項式時間內求解，則它的最優化問題也同樣不能在確定的多項式時間內求解。
在進一步討論之前，為了量測復雜度必須先統一參數n。假設n是算法的輸入長度；還假定所有的輸入都是整數。有理數輸入可以視作一對整數。一般說輸入量的長度是以該量的二進制表示度量的，即如果輸入量是十進制的10，相應的二進制表示就是1010，因此它的長度就是4。對于正整數k，用二進制形式表示時的長度就是|_ _|+1。0的長度規定為1。算法輸入的大小或長度n是指輸入的各個數長度的總和。因此，用不同的進位制時的長度是不同的，以r為基的正整數k，其長度為|_ _|。在十進制中(r＝10) 數100的長度為 100+1＝3。因為 ＝ / ，于是以r (r>1)為基輸入的長度為c (r)·n，其中n是以二進制表示時的長度，c(r) 是對于給定r后的一個常數。
當使用基r=1給定輸入量時，則稱此輸入是一進制形式的。在一進制形式中，數5的輸入形式是11111。于是正整數k的長度即為k。
注意 ：一進制形式輸入的長度與其相應的基為r(r>1)的輸入的長度間具有指數關系。
[例]：(最大集團) 最大集團判定問題的輸入可以看作是一個邊的序列和一個整數k。
e(g)內的每條邊又是一對數值(i，j)。對于每條邊(i，j)，如果采用二進制表示，則其輸入的大小為 + +2。于是任一實例的輸人大小為
n＝
注意：如果g只有一個連通分圖，則n≥|v|。于是對于某個多項式p()，若這個判定問題不能由一個復雜度為p(n)的算法求解，則它也不能被復雜度為p(|v|)的算法求解。
[例]： (0／1背包) 假設pi，wi，m和r均為整數，背包判定問題輸入量的大小為
m=
其中，m≥n。如果輸入量用一進制形式給出，則輸人大小s為 +m+r。對于某個多項式p()，背包的判定問題和最優化問題均可在p(s)的時間內求解；但對于某個多項式p()還不知道有復雜度為o(p(n))的算法。
下面給出不確定算法復雜度的形式定義。
定義：一個不確定算法所需的時間是指當存在一選擇序列導致一成功的完成時，為了完成任意給定的一個輸入而達到成功完成所需步驟的最小值。在不可能成功完成的情況下所需的時間是o(1)。假如對于所有的大小為n (n≥ )的輸入，導致成功完成需要的時間至多為c·f(n)，其中c和 是兩個常數，則這個不確定算法的復雜度為o(f(n))。
在上述定義中，假定每個計算步驟的開銷是固定的。在面向字處理的計算機中，每個宇的有限性確保了固定開銷。當每步開銷不固定時，則應考慮各條指令的開銷。例如兩個m位的數相加花費的時間為o(m)，而按經典方法將這兩數相乘，則花費的時間為o( )等等。為了弄清注意這一問題的必要性，下面來考察子集和數判定問題的確定算法sum。它用了一個m+1位的字s。當且僅當整數a(j)，1≤j≤n，不存在和數為i的子集時s的第i位為0。s的位數按從右到左的次序編碼為0，1，2，…，m，且s的第0位總取值為1。函數shift把s中的各位均向左移動a(o位。這個算法的總步數只有o(n)。然而每步都要移動數據m+1位，因此在一臺傳統的計算機上每步實際上所需的時間為o(m)。假設對于一個大小固定的字，每個基本操作都需要一個單位的時間，那末該算法的真實復雜度是o(nm)而不是o(n)。
[算法]：子集和數判定的確定算法 [動畫]
procedure sum(a，n，m)
integer a(n)，s，n，m
s<-1／s是一個有m+1位的字，第0位是1／／
for iß1 to n do
sßs or shift(s，a(i))
repeat
if mth bit in s=0 then print(‘no subset sums to m’)
else print(‘a subset sums to m，)
endif
end sum
不確定算法的優點是對于那些用確定算法寫起來非常復雜的問題可以很容易地寫出它們的不確定算法。事實上，對于許多可以通過系統檢索指數大小解空間來確定地求解的問題，要得到它們的多項式時間的不確定算法是很容易的。
[例]：(背包判定問題) 過程dkP(算法8．3)是背包問題的一個不確定的多項式時間算法。第1～3行將0／1值賦給x(0，1≤i≤n。第4行檢查賦值的可行性并且查看所導致的效益值是否至少為r。當且僅當判定問題的答案為“是”，才可能是一個成功的終止。時間復雜度是o(n)。如果m是用二進制表示的輸入長度，則時間是o (m)。
[算法]：背包問題的不確定算法[動畫]
procedure dkP(P，w，n，m，r，x)
integer P(n)，w(n)，r，x(n)，n，m，i
x(i)ßchoice (0，1)
if >m or <r then failure
else success
end dkP
[例]：(最大集團) 過程dck(算法8．4)是此集團判定問題的一個不確定算法。算法開始時試探形成一個具有k個不同結點的集合，然后測試這些結點是否構成一個完全子圖。若g是由其鄰接矩陣和|v|＝n所給出，則輸入長度m為 + +2。易于看出第2～6行的不確定的執行時間為o(n)。第7～10行的時間為o( )。于是總時間為o(n+ )＝o( )＝o(m)。對于這個問題，已知它有多項式時間的確定算法。
[算法]：集團的不確定算法[動畫]
procedure dck(g，n，k)
1 sß ／s的初值為空’集合／／
2 for iß1 to k do／選擇k個不同的結點／／
3 tßchoice (1：n)
4 if t s then failure endif
5 sßs t／／將t加到集合s"
6 repeat ／／此處s含有k個不同結點的下標／／
7 for使得i s，j s的每一對(i,j) and i j do
8 if (i,j)不是此圖的邊
9 then failure endif
10 repeat
end dck
[算法]： 可滿足性的不確定算法 [動畫]
procedure eval(e，n)
／／判定命題e是否為可滿足的。變量為 ，1≤i≤n／／
boolean x (n)
for iß1 to n do／／選取一組真值指派／／
ßchoice (true，false)
if e ( )＝true then success／／可滿足的／／
else failure
end eval