NP问题的通用多项式算法

王海东

(天津市北方调查策划事务所 300050)

不管拥有多么强大的计算能力和多么先进的计算工具，人类面临的所有计算问题都可以分为两类.这两类计算问题就是P类问题和E类问题.P类问题就是给出计算结果的时间为多项式时间的计算问题.多项式时间就是用多项式时间函数表示的计算时间.多项式时间函数就是将计算步骤视为多项式变量的时间函数.E类问题就是给出计算结果的时间为指数时间的计算问题.指数时间就是用指数时间函数表示的计算时间.指数时间函数就是将计算步骤视为指数变量的时间函数.

令t代表计算时间，s代表计算步骤，C代表重复计算次数，N代表计算数据位数，k代表任意正整数，P代表多项式时间，E代表指数时间，我们可以用以下公式表示多项式时间和指数时间：

从这个公式来看，在计算数据位数较小的情况下，P类问题和E类问题在理论上都是人类可以有效解决的计算问题.但是，在计算数据位数较大的情况下，P类问题在理论上仍然是人类可以有效解决的计算问题，E类问题在理论上则不是人类可以有效解决的计算问题了.因为，E类问题计算时间的增长速度不仅远远超过了P类问题计算时间的增长速度，而且有可能远远超过几代甚至十几代或几十代人类的生存时间.

那么，怎样才能使E类问题像P类问题一样，不管计算数据位数如何发生变化，都能在理论上成为人类可以有效解决的计算问题呢？显然，回答这个问题的关键在于是否存在NP问题.NP问题就是具有非确定性多项式时间的计算问题.非确定性多项式时间就是可以采取非确定性方法有效解决各种E类问题的多项式时间.非确定性方法就是通过一次计算就能从可供选择的众多答案中找到正确答案的计算方法.

假定不存在NP问题，人类就只能采取计算近似值或特征值的替代方法，来解决那些在理论上不能有效解决的E类问题了.假定存在NP问题，另一个问题就会随之而来：NP问题到底是不是一种P类问题？如果NP问题是一种P类问题，NP问题就肯定具有NP完全性.如果NP问题不是一种P类问题，NP问题就肯定不具有NP完全性.NP完全性是指：存在着一种具有特殊性质的NP问题.只要这种NP问题存在着一种多项式算法，这种多项式算法就可以被推广到其他任何一种NP问题之中.因为，所有NP问题在理论上都存在着某种相同的多项式时间.多项式算法就是适用于多项式时间的计算方法.由于NP完全性意味着NP问题可能存在通用多项式算法，所以能否找到这种通用多项式算法就变成了回答上述所有问题的关键.

下面，我们就以流动推销员问题为例来寻找NP问题的通用多项式算法.

流动推销员问题是奥地利数学家门格提出的一个计算问题.这个计算问题在各种计算领域之中具有广泛的代表性.我们可以用一个n阶方阵来表述这个计算问题：

其中，主对角线元素为零元素，非主对角线元素为非零元素.第一组行列元素代表第一座城市与其他城市之间的往返距离，第二组行列元素代表第二座城市与其他城市之间的往返距离，第三组行列元素代表第三座城市与其他城市之间的往返距离，以此类推直至第n组行列元素.

假定流动推销员居住在第一座城市，其他城市都是流动推销员从事推销工作的城市.所谓流动推销员问题，就是从第一座城市与其他城市之间的所有往返路线中选出一条最短路线的计算问题.

那么，第一座城市与其他城市之间到底有多少往返路线呢？显然，第一座城市与其他城市之间的往返路线数等于(n-1)的阶乘数.从这个阶乘数来看，当n的位数达到两位数之后，流动推销员问题就会变成流动推销员本人无法有效解决的E类问题了.因此，流动推销员问题是一个与NP问题有关的计算问题.由于流动推销员问题是一个与NP问题有关的计算问题，所以流动推销员问题也是一个与NP完全性有关的计算问题.

问题是和解决问题的方法一起产生的.既然流动推销员问题可以用一个n阶方阵表述出来，这个n阶方阵就肯定包含着有效解决这个问题的某种方法.这种方法来自于这个n阶方阵为我们提供的两个重要信息.

第一个重要信息是：主对角线左右两侧的非零行列元素都属于对称元素.如果将穿越主对角线的往返路线视为无效路线，主对角线左右两侧就存在着两套相互对称的往返路线.只要从主对角线一侧找出一条往返路线，就可以从主对角线另一侧找出另一条往返距离相同的往返路线.虽然第一座城市与其他城市之间的往返路线数等于(n-1)的阶乘数，但是可供选择的往返路线数仅仅等于这个阶乘数的二分之一.

第二个重要信息是：主对角线左右两侧的非零行列元素都包含最短距离.如果将包含最短距离的非零行列元素集中排列在主对角线的左上角或右下角，就可以利用这些非零行列元素的相邻关系构造出一条最短距离最多的往返路线.由于每条往返路线的往返距离既有可能来自最短距离又有可能来自非最短距离，又由于最短距离的增加意味着非最短距离的减少和往返距离的缩短，所以最短距离最多的往返路线就是一条最短路线.

根据以上分析，我们可以推出两个十分重要的计算定理.这两个计算定理就是最短路线选择定理和最短路线构造定理.

最短路线选择定理是指：某条往返路线为最短路线当且仅当最短距离数超过其他任何一条往返路线.

令u代表一组最短距离，v代表一组非最短距离，L代表一组往返路线，minL代表最短路线，我们可以用以下方法来证明最短路线选择定理：

已知

u=(u1,u2,u3,…,un)

v=(v1,v2,v3,…,vn)

L=(L1,L2,L3,…,Ln)

又知

u1

L1=u1+v2+v3+v4+…+vn

L2=u1+u2+v3+v4+…+vn

L3=u1+u2+u3+v4+…+vn

……

Ln=u1+u2+u3+u4+…+un

因此

minL=Ln

证毕.

最短路线构造定理是指：在一个主对角线元素为零元素、非主对角线元素为非零元素的n阶方阵中，只有将包含最短距离的非零行列元素集中排列在主对角线的左上角或右下角，才能用最短时间构造出一条最短距离最多的往返路线.

我们可以用一个流动推销员问题的具体案例来证明最短路线构造定理：

已知

又知

x13=x31

x23=x32

x14=x41

x24=x42

因此

minL=x13+x23+x24+x14+…+x31+x32+x42+x41

证毕

由此可见，最短路线选择定理和最短路线构造定理就是流动推销员问题的多项式算法.流动推销员问题的多项式算法就是NP问题的通用多项式算法.因为，流动推销员问题就是一种具有特殊性质的NP问题.任何一种可以化为流动推销员问题的NP问题，都可以用最短路线选择定理和最短路线构造定理来解决.

在找到了NP问题的通用多项式算法之后，我们就可以对上述所有问题做出回答了：由于NP问题存在通用多项式算法，所以NP问题就是一种P类问题.这种P类问题不仅大量存在于各种计算领域，而且确实有可能用非确定性方法一次给出正确答案.这种非确定性方法就是符合最短路线选择定理和最短路线构造定理的计算方法.