姜咏江

P与NP问题是美国克雷数学所悬赏百万美元大奖的七大世界难题之一。简单地说，用计算机在多项式时间内求出解的一类问题，称为P类问题；而在多项式时间可以验证是否是解的问题，称为NP类问题。回答P与NP是同一类问题吗？这就是P与NP问题。

这个看似简单的问题，为何会成为公开的世界难题？我认为原因是人们行进到了不易解决的方向上所致。这首先是一个不连续的数学问题，想用连续数的理论去解决，自然是徒劳的事情。

我们先说清楚几个概念。

1. 可判定问题：能够知道对与错的问题。

   显然，P与NP类问题都是可判定问题。又P类问题求解过程就能验证对与错，因而P类问题就是NP类问题。

   2. 多项式：k是一个常数，a₁x+a₂x²+...+a_nx^k叫多项式。

   如果将k理解成一个随着变量数n而变化的量，那就不准确理解P与NP问题中所说的多项式含义了。因为由二项式定理可知：(1+1)ⁿ=(ⁿ₀)+(ⁿ₁)+...+(ⁿ_k)+...+(ⁿ_n)，等式左面是2ⁿ，是一个关于n的指数函数。右面虽然写成了多个项，但已不是P与NP问题中多项式的概念，其中k项之后不能算数。

1. 计算机程序执行快慢：同一计算机对同一问题不同设计程序执行快慢的发展趋势。

   例如一个程序对某问题能够求出解的时间是T=2ⁿ，另一程序对同一问题的求解时间是T=n⁴，此时不能笼统地说哪个程序快。因为从2ⁿ=n⁴可知，若二进制 n=2^k，就有2^k=4k 得k=4。即当n大于16时，才有2ⁿ>n⁴。T=n⁴这个程序才会比T=2ⁿ程序快。所以P与NP问题要研究影响程序执行快慢因素n变大的过程，什么样的程序执行快。知道了这些，就会明白程序执行如果是多项式时间的就会快。

2. 问题通俗解释是，对n个逻辑变量验证可能结果对错，最坏情况是T=2ⁿ（穷举法），也就是说能够用穷举法找到答案的问题（NP）能否在多项式时间得到答案。

有n个逻辑变量，下面公式（1）用“+”表示或运算符，用“’”表示非运算符，将与运算符省略了。

公式（1）的逻辑运算式叫合取范式。

合取范式能不能有一组变量值是其结果是1（“真”），这就是SAT问题。

显然，我们可以将2ⁿ个不同的n位二进制数带入（1）右端检验结果，一定可以找到答案，这是穷举法，是2ⁿ指数时间的算法。

SAT问题有没有多项式时间的算法？以往，人们没有找到，因而才成了典型的寻找NP是否是P问题的实例。人们已经证明了，如果SAT 问题有多项式时间算法，那么NP类问题就是P类问题。

实际当中许多问题是不能够用连续的实数来描述的。这些问题中常常是只需要回答元素的有与无。各种事物的组成分析都属于这种元素存在问题。有些问题在元素存在分析的基础上，又会加入某种特性的描述，在这种特性之下来求极值。例如，邮差问题、子集和问题等，必须先解决元素存在，在存在的基础上需求最优解。这些问题难就难在解决相关元素关联存在的问题上。

NP类问题首先是纯离散的问题。这类问题中的基础是先找出事物的存在，然后才是寻求属性的极值。而以往，人们追求用连续数学描述，脱离了问题的首要实际。例如，采用概率形式的算法并不能求出精确值，而NP问题要求结果是精确值。

纯离散问题有两大特点。第一，元素数量有限。第二，元素间总有一定的存在结构。元素存在的结构形成事物。事物就是某种条件下的元素子集。某种子集有没有，找到它常常是问题的难点。例如，SAT 问题、哈密顿回路问题、顶点覆盖问题、团问题、子集和问题、邮差问题等。

要做结构分析，数据抽象是关键。其中最好的莫过于用0和1来表示元素的存在与不存在。这样就可以将这些存在分析问题，转化成二进制数的有限位分析，从看似无结构的状态中，显现出离散元素构成事物的内在结构。对这些由0和1 描述表现出来的规律，再做进一步的分析，就容易达到光辉的顶点。对P与NP问题的解决，这一定是一条可行之路。

请参阅：http://blog.sciencenet.cn/blog-340399-1070984.html

2017-8-22