一、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

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个不同结点的集合，然后测试这些结点是否构成一个完全子图。若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

  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