一、nP-問題的基本概念

 

       本章的內(nèi)容包括了在算法研究方面的最重要的基本理論。這些基本理論對于計算機科學(xué)

家、電氣工程師和從事運籌學(xué)等方面的工作者都是十分有用的。因此，凡是在這些領(lǐng)域里的工作者建議讀本章的內(nèi)容。  

不過，在閱讀本章之前，讀者應(yīng)熟悉以下基本概念：一是算法的事先分析計算時間，它是在所給定的不同數(shù)據(jù)集下，通過研究算法中語句．的執(zhí)行頻率而得到的，二是算法時間復(fù)雜度的數(shù)量級以及它們的漸近表示。如果一個算法在輸入量為n的情況下計算時間為t(n)，則記作t(n)＝o(f(n))，它表示時間以函數(shù)f(n)為上界。t(n)= (g(n))表示時間以函數(shù)g(n)為下界。這些概念在第一章都作過詳細(xì)的闡述。

       另一個重要概念是關(guān)于兩類問題的區(qū)別，其中第一類的求解只需多項式時間的算法，而第二類的求解則需要非多項式時間的算法(即，g(n)大于任何多項式)。對于已遇到和作過研究的許多問題，可按求解它們的最好算法所用計算時間分為兩類。第一類問題的求解只需低次多項式時間。例如本書前面講過的有序檢索的計算時間為o(1ogn)，分類為o(nlogn)，矩陣乘法為o( )等。第二類問題則包括那些迄今已知的最好算法所需時間為非多項式時間的問題。例如貨郎擔(dān)問題和背包問題的時間復(fù)雜度分別為o( )和o( )。對于第二類問題，人們一直在尋求更有效的算法，但至今還沒有誰開發(fā)出一個具有多項式時間復(fù)雜度的算法。指出這一點是十分重要的，因為算法的時間復(fù)雜度一旦大于多項式時間(典型的時間復(fù)雜度是指數(shù)時間)，算法的執(zhí)行時間就會隨n的增大面急劇增加，以致即使是中等規(guī)模的問題也不能解出。

       本章所討論的nP-完全性理論，對于第二類問題，既不能給出使其獲得多項式時間的方法，也不說明這樣的算法不存在。取而代之的是證明了許多尚不知其有多項式時間算法的問題在計算上是相關(guān)的。實際上，我們建立了分別叫做nP-難度的和nP-完全的兩類問題。一個nP-完全的問題具有如下性質(zhì)：它可以在多項式時間內(nèi)求解，當(dāng)且僅當(dāng)所有其它的nP-完全問題也可在多項式時間內(nèi)求解。假如有朝一日某個nP-難度的問題可以被一個多項式時間的算法求解，那末所有的nP—完全問題就都可以在多項式時間內(nèi)求解。下面將會看到，一切nP-完全的問題都是nP-難度的問題，但一切nP-難度的問題并不都是nP-完全的。

 

二、不確定的算法

 

      到目前為止在已用過的算法中，每種運算的結(jié)果都是唯一確定的，這樣的算法叫做確定的算法(deterministic algorithm)。這種算法和在計算機上執(zhí)行程序的方式是一致的。從理論的角度看，對于每種運算的結(jié)果“唯一確定”這一限制可以取消。即可以允許算法每種運算的結(jié)果不是唯一確定的，而是受限于某個特定的可能性集合。執(zhí)行這些運算的機器可以根據(jù)稍后定義的終止條件選擇可能性集合中的一個作為結(jié)果。這就引出了所謂不確定的算法 (nondeterministic algorithm)。為了詳細(xì)說明這種算法，在sParks中引進(jìn)一個新函數(shù)和兩條新語句：

           choice (s)…任意選取集合s中的一個元素。

            failure…發(fā)出不成功完成的信號。

            success…發(fā)出成功完成的信號。

       賦值語句xßchoice (1：n)使x內(nèi)的結(jié)果是區(qū)域[1，n]中的任一整數(shù)(沒有規(guī)則限定這種選擇是如何作出的)。failure和success的信號用來定義此算法的一種計算，這兩條語句等價于stop語句，但不能起return語句的作用。每當(dāng)有一組選擇導(dǎo)致成功的完成時，總作出這樣的一組選擇并使算法成功地終止。當(dāng)且僅當(dāng)不存在任何一組選擇會導(dǎo)致成功的信號，那末不確定的算法不成功地終止。choice，success和failure的計算時間取為o (1)。能按這種方式執(zhí)行不確定算法的機器稱為不確定機(nondeterministic machine)。然而這里所定義的不確定機實際上是不存在的，因此通過直覺可以感到這類問題不可能用“快速的”確定算法求解。

   

三、本節(jié)實例

 

[例]：（檢索）考察在給定的元素集a(1：n)中，n≥1，檢索元素x的檢索問題。應(yīng)確定下標(biāo)j，使得a(j)＝x，或者當(dāng)x不在a中時有j＝0。此問題的一個不確定算法為

    jßchoice (1：n)

    if a(j)=x then print(j)；success endif 

    print (‘0’)；failure

       由上述定義的不確定算法當(dāng)且僅當(dāng)不存在一個j使得a(j)＝x時輸出“0”。此算法有不確定的復(fù)雜度o(1)。

         注意：由于a是無序的，因此確定的檢索算法的復(fù)雜度為 (n)。

[例]：(分類) 設(shè)a(i)，1≤i≤n，是一個尚未分類的正整數(shù)集。不確定的算法nsort(a，n)將這些數(shù)按非降次序分類并輸出。為方便起見，采用一輔助數(shù)組b(1：n)。第1行將b初始化為零。在第2~6行的循環(huán)中，每個a(i)的值都賦給b中的某個位置，第3行不確定地定出這個位置，第4行弄清b(j)是否還沒用過。因此b中整數(shù)的次序是a中初始次序的某種排列。第7~9行驗證b是否已按非降次序分類。當(dāng)且僅當(dāng)整數(shù)以非降次序輸出時，算法成功地完成。由于第3行對于這種輸出次序總存在一組選擇，因此算法nsort是一個分類算法，它的復(fù)雜度為o(n)。回憶前面講過的各種確定的分類算法可知它們的復(fù)雜度應(yīng)為 (nlogn)。

[算法]：不確定的分類算法 [動畫]

  procedure nsort(a，n)

    ／／對n個正整數(shù)分類／／

    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

       通過允許作不受限制的并行計算可以對不確定的算法作出確定的解釋。每當(dāng)要作某種選擇時，算法就好像給自己復(fù)制了若干副本，每種可能的選擇有一個副本，于是許多副本同時被執(zhí)行。第一個獲得成功完成的副本，將引起其它所有副本的計算終止。如果一個副本獲得不成功的完成則只該副本終止。前面說過success和failure信號相當(dāng)于確定算法中的stop語句，但它們不能用來取代return語句。上述解釋是為了便于讀者理解不確定算法。

      注意： 對一臺不確定機來說，當(dāng)算法每次作某種選擇時，它實際上是什么副本都不作的，只是在每次作某種選擇時，具有從可選集合中選擇出一個“正確的”元素的能力(如果這樣的元素存在的話)。一個“正確的”元素是相對于導(dǎo)致一成功終止的最短選擇序列而定義的。在不存在導(dǎo)致成功終止的選擇序列的情況下，則假定算法是在一個單位時間內(nèi)終止并且輸出“計算不成功”。只要有成功終止的可能，一臺不確定機就會以最短的選擇序列導(dǎo)致成功的終止。因為這種不確定機本來就是虛構(gòu)和假想的，所以沒有必要去注意機器在每一步是如何作出正確選擇的。

       完全有可能構(gòu)造出一些這樣的不確定算法，它們的多種不同的選擇序列都會導(dǎo)致成功的完成。例8．2的過程nsort就是這樣的一個算法。如果整數(shù)a（i）有許多是相同的，那末在一個分類序列中將出現(xiàn)許多不同的排列。如果不是按已分好類的次序輸出這些a（i），而是輸出所用的排列，那末這樣的輸出將不是唯一確定的。今后只關(guān)心那些產(chǎn)生唯一輸出的不確定算法，特別是只研究那些不確定的判定算法(nondeteministic decision algorithm)。這些算法只產(chǎn)生“0”或“1”作為輸出，即作二值決策，前者當(dāng)且僅當(dāng)沒有一種選擇序列可導(dǎo)致一個成功的完成，后者當(dāng)且僅當(dāng)一個成功的完成被產(chǎn)生。輸出語句隱含于success和failure之中。在判定算法中不允許有明顯的輸出語句。顯然，早先對不確定計算的定義意味著一個判定算法的輸出由輸入?yún)?shù)和算法本身的規(guī)范唯一地確定。

       雖然上面所述的判定算法的概念看來似乎限制過嚴(yán)，但事實上許多最優(yōu)化問題都可以改寫成判定問題并使其具有如下性質(zhì)；該判定問題可以在多項式時間內(nèi)求解，當(dāng)且僅當(dāng)與它相應(yīng)的最優(yōu)化問題可以在多項式時間內(nèi)求解。從另一方面說，如果判定問題不能在多項式時間內(nèi)求解，那末與它相應(yīng)的最優(yōu)化問題也不能在多項式時間內(nèi)求解。

[例]： (最大集團) 圖g＝(v，e)的最大完全子圖叫作g的一個集團(clique)。集團的大小用所含的結(jié)點數(shù)來量度。最大集團問題即為確定g內(nèi)最大集團的大小問題。與之對應(yīng)的判定問題是，對于某個給定的k，確定g是否有一個大小至少為k的集團。令dcliq—ue(g，k)是此集團判定問題的一個確定的判定算法。假設(shè)g的結(jié)點數(shù)為n，g內(nèi)最大集團的大小可在多次應(yīng)用dclique(g，k)而求得。對于每個k，k=n，n一1，n一2，…直到dcliclue輸出l為止，過程dclique都要被引用一次。如果dclique的時間復(fù)雜度為（b)，則最大集團的大小可在n，f(n)時間內(nèi)求出二假如最大集團的大小可以在g(n)時間內(nèi)確定，于是其判定問題也可在g(n)時間內(nèi)解出。因此最大集團問題可在多項式時間內(nèi)求解，當(dāng)且僅當(dāng)集團的判定問題可在多項式時間內(nèi)求解。  

[例]： (0／1背包) 背包的判定問題是確定對 ，1≤i≤n，是否存在一組o／1的賦值，使得 ≥r和 ≤m。r是一個給定的數(shù)，而這些 及 都是非負(fù)的數(shù)。顯然，如果背包的判定問題不能在確定的多項式時間內(nèi)求解，則它的最優(yōu)化問題也同樣不能在確定的多項式時間內(nèi)求解。

        在進(jìn)一步討論之前，為了量測復(fù)雜度必須先統(tǒng)一參數(shù)n。假設(shè)n是算法的輸入長度；還假定所有的輸入都是整數(shù)。有理數(shù)輸入可以視作一對整數(shù)。一般說輸入量的長度是以該量的二進(jìn)制表示度量的，即如果輸入量是十進(jìn)制的10，相應(yīng)的二進(jìn)制表示就是1010，因此它的長度就是4。對于正整數(shù)k，用二進(jìn)制形式表示時的長度就是|_ _|+1。0的長度規(guī)定為1。算法輸入的大小或長度n是指輸入的各個數(shù)長度的總和。因此，用不同的進(jìn)位制時的長度是不同的，以r為基的正整數(shù)k，其長度為|_ _|。在十進(jìn)制中(r＝10) 數(shù)100的長度為 100+1＝3。因為 ＝ / ，于是以r (r>1)為基輸入的長度為c (r)·n，其中n是以二進(jìn)制表示時的長度，c(r) 是對于給定r后的一個常數(shù)。

       當(dāng)使用基r=1給定輸入量時，則稱此輸入是一進(jìn)制形式的。在一進(jìn)制形式中，數(shù)5的輸入形式是11111。于是正整數(shù)k的長度即為k。

     注意 ：一進(jìn)制形式輸入的長度與其相應(yīng)的基為r(r>1)的輸入的長度間具有指數(shù)關(guān)系。

[例]：(最大集團) 最大集團判定問題的輸入可以看作是一個邊的序列和一個整數(shù)k。

 e(g)內(nèi)的每條邊又是一對數(shù)值(i，j)。對于每條邊(i，j)，如果采用二進(jìn)制表示，則其輸入的大小為 + +2。于是任一實例的輸人大小為

       n＝

注意：如果g只有一個連通分圖，則n≥|v|。于是對于某個多項式p()，若這個判定問題不能由一個復(fù)雜度為p(n)的算法求解，則它也不能被復(fù)雜度為p(|v|)的算法求解。

[例]： (0／1背包) 假設(shè)pi，wi，m和r均為整數(shù)，背包判定問題輸入量的大小為

  m=

其中，m≥n。如果輸入量用一進(jìn)制形式給出，則輸人大小s為 +m+r。對于某個多項式p()，背包的判定問題和最優(yōu)化問題均可在p(s)的時間內(nèi)求解；但對于某個多項式p()還不知道有復(fù)雜度為o(p(n))的算法。

       下面給出不確定算法復(fù)雜度的形式定義。

     定義：一個不確定算法所需的時間是指當(dāng)存在一選擇序列導(dǎo)致一成功的完成時，為了完成任意給定的一個輸入而達(dá)到成功完成所需步驟的最小值。在不可能成功完成的情況下所需的時間是o(1)。假如對于所有的大小為n (n≥ )的輸入，導(dǎo)致成功完成需要的時間至多為c·f(n)，其中c和 是兩個常數(shù)，則這個不確定算法的復(fù)雜度為o(f(n))。

         在上述定義中，假定每個計算步驟的開銷是固定的。在面向字處理的計算機中，每個宇的有限性確保了固定開銷。當(dāng)每步開銷不固定時，則應(yīng)考慮各條指令的開銷。例如兩個m位的數(shù)相加花費的時間為o(m)，而按經(jīng)典方法將這兩數(shù)相乘，則花費的時間為o( )等等。為了弄清注意這一問題的必要性，下面來考察子集和數(shù)判定問題的確定算法sum。它用了一個m+1位的字s。當(dāng)且僅當(dāng)整數(shù)a(j)，1≤j≤n，不存在和數(shù)為i的子集時s的第i位為0。s的位數(shù)按從右到左的次序編碼為0，1，2，…，m，且s的第0位總?cè)≈禐?/span>1。函數(shù)shift把s中的各位均向左移動a(o位。這個算法的總步數(shù)只有o(n)。然而每步都要移動數(shù)據(jù)m+1位，因此在一臺傳統(tǒng)的計算機上每步實際上所需的時間為o(m)。假設(shè)對于一個大小固定的字，每個基本操作都需要一個單位的時間，那末該算法的真實復(fù)雜度是o(nm)而不是o(n)。

[算法]：子集和數(shù)判定的確定算法 [動畫]

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

    不確定算法的優(yōu)點是對于那些用確定算法寫起來非常復(fù)雜的問題可以很容易地寫出它們的不確定算法。事實上，對于許多可以通過系統(tǒng)檢索指數(shù)大小解空間來確定地求解的問題，要得到它們的多項式時間的不確定算法是很容易的。

[例]：(背包判定問題) 過程dkP(算法8．3)是背包問題的一個不確定的多項式時間算法。第1～3行將0／1值賦給x(0，1≤i≤n。第4行檢查賦值的可行性并且查看所導(dǎo)致的效益值是否至少為r。當(dāng)且僅當(dāng)判定問題的答案為“是”，才可能是一個成功的終止。時間復(fù)雜度是o(n)。如果m是用二進(jìn)制表示的輸入長度，則時間是o (m)。

[算法]：背包問題的不確定算法[動畫]

   procedure dkP(P，w，n，m，r，x)

integer P(n)，w(n)，r，x(n)，n，m，i

for iß1 to n do

 x(i)ßchoice (0，1)   

repeat    

if >m or <r then failure

else success

  endif

end dkP

[例]：(最大集團) 過程dck(算法8．4)是此集團判定問題的一個不確定算法。算法開始時試探形成一個具有k個不同結(jié)點的集合，然后測試這些結(jié)點是否構(gòu)成一個完全子圖。若g是由其鄰接矩陣和|v|＝n所給出，則輸入長度m為 + +2。易于看出第2～6行的不確定的執(zhí)行時間為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個不同的結(jié)點／／

    3    tßchoice (1：n)   

    4    if t s then failure endif

  5              sßs t／／將t加到集合s"

  6    repeat ／／此處s含有k個不同結(jié)點的下標(biāo)／／

     7    for使得i s，j s的每一對(i,j) and i j do

  8    if (i,j)不是此圖的邊

     9     then failure endif

  10  repeat

  11  success

end dck

[算法]： 可滿足性的不確定算法 [動畫]

    procedure eval(e，n)

    ／／判定命題e是否為可滿足的。變量為 ，1≤i≤n／／

    boolean x (n)

    for iß1 to n do／／選取一組真值指派／／

    ßchoice (true，false)

    repeat

    if e ( )＝true then success／／可滿足的／／

    else failure

    endif   

    end eval