算法中的NP问题
IT商界
上期我们结合了几个具体的例子了解了算法的时间复杂性的分析和描述方法。本期我们来讨论一下NP问题。
NP问题又称为非多项式界问题。它是相对于多项式界问题(又称P问题)而言的。对于一个算法如果它的时间复杂度是问题规模n的多项式函数，那我们称这个算法叫多项式界算法。
可以考虑，对于一个多项式界的算法，如果问题的规模为n，则存在一个多项式P，使这个算法在最坏的情况下至多做P(n)次基本运算。那么，如果一个问题具有一个多项式界的算法，则这个问题是多项式界问题。NP问题就是还没有找到多项式界算法的问题的统称。这里我们需要阐明一个概念：问题是否存在一个非多项式界的算法不能作为判断它是不是NP问题的依据。例如在求解n阶的线性代数方程组时，如果用克莱姆规则求解就需要做(n2-1)n!次乘法，这是一个非多项式界算法。但求解线性代数方程组问题确实为多项式界问题，这是因为它存在其他的多项式界的算法，例如高斯消元法。
在实际问题中，一些复杂问题往往是若干简单问题的组合，解决这些复杂问题的算法也可以是解决若干简单问题的算法组合而成的。这里笔者要提出一条结论：对于任意一个由几个多项式界算法用加、乘和复算法等方法组合而成的算法依然是多项式界的。
这里还有一个概念需要解释一下就是NP完全问题。假设在NP类问题中，如果有一个问题Q存在一个算法A，且对于NP中的任何问题都可以找到一个包括以子程序或过程形式调用A的算法，并且这个算法的运算次数(调用A只计一次运算，即不计A本身的运算次数)是多项式为界的。那么问题Q被称为是NP完全的。对于NP完全问题的判定有一个定理：设Q是NP完全的，则：
1.Q∈P当且仅当P=NP；
2.若Q∝pQ'，且Q'∈NP，则Q'是NP完全的。(如果问题A经过适当的变换可以转换成问题B，则可记为A∝B，如果A转换到B的过程是多项式界的话，则可记为A∝pB)
上面的定理主要说明了两个问题：
一是使用上面的定理判断NP问题完全性的方法只在有了第一个NP完全问题之后才能使用，很幸运的是前人已经找到了第一个NP完全问题，也就是著名的“布尔表达式的可满足性问题”。
一个是如果在NP完全类问题中存在一个问题是多项式界的，则NP类中的每一个问题都是多项式界的，就有NP=P。但到目前为止，虽然已找到很多NP完全问题，但都还未找到多项式界算法。
下面举几个典型的NP完全问题：
一、 布尔表达式的可满足性问题
对于k个布尔变量X1,......Xk的m个布尔表达式A1,A2......Am。是否存在各布尔变量Xi(1≤i≤k)的一种0或1的赋值，使每个布尔表达式Ai(1≤i≤m)都取1。
二、装箱问题
设有n件物品，每件物品的体积分别是S1,S2......,Sn，且0＜Si≤1(i=1,2......n)。现在有一批箱子，每只箱子的容量是1个单位。现在要求：能够容纳这n件物品的箱子至少需要多少只？或者说，给定正整数M，问能否把这n件物品放入此M只箱子里。
三、背包问题
给定n个尺寸为S1,S2......Sn的物体和容量为C的背包，其中S1,S2,......Sn和C均为正整数。问题是：在n个物体中选取一部分，尽可能多地填满容量为C的背包。