P 与 NP 问题为什么会成为百万美元大奖的世界难题？ 姜咏江 P 与 NP 问题是美国克雷数学所悬赏百万美元大奖的七大世界难题之一。简单地说，用计算机在多项式时间内求出解的一类问题，称为 P 类问题；而在多项式时间可以验证是否是解的问题，称为 NP 类问题。回答 P 与 NP 是同一类问题吗？这就是 P 与 NP 问题。 这个看似简单的问题，为何会成为公开的世界难题？我认为原因是人们行进到了不易解决的方向上所致。这首先是一个不连续的数学问题，想用连续数的理论去解决，自然是徒劳的事情。 一、一些基本概念的理解 我们先说清楚几个概念。 可判定问题：能够知道对与错的问题。 显然， P 与 NP 类问题都是可判定问题。又 P 类问题求解过程就能验证对与错，因而 P 类问题就是 NP 类问题。 2. 多项式： k 是一个常数， a 1 x+a 2 x 2 +...+a n x k 叫多项式。 如果将 k 理解成一个随着变量数 n 而变化的量，那就不准确理解 P 与 NP 问题中所说的多项式含义了。因为由二项式定理可知： (1+1) n =( n 0 )+( n 1 )+...+( n k )+...+( n n ) ，等式左面是 2 n ，是一个关于 n 的指数函数。右面虽然写成了多个项，但已不是 P 与 NP 问题中多项式的概念，其中 k 项之后不能算数。 计算机程序执行快慢：同一计算机对同一问题不同设计程序执行快慢的发展趋势。 例如一个程序对某问题能够求出解的时间是 T=2 n ，另一程序对同一问题的求解时间是 T=n 4 ，此时不能笼统地说哪个程序快。因为从 2 n =n 4 可知，若二进制 n=2 k ，就有 2 k =4k 得 k=4 。即当 n 大于 16 时，才有 2 n n 4 。 T=n 4 这个程序才会比 T=2 n 程序快。所以 P 与 NP 问题要研究影响程序执行快慢因素 n 变大的过程，什么样的程序执行快。知道了这些，就会明白程序执行如果是多项式时间的就会快。 问题通俗解释是，对 n 个逻辑变量验证可能结果对错，最坏情况是 T=2 n （穷举法），也就是说能够用穷举法找到答案的问题（ NP ）能否在多项式时间得到答案。 二、 最看似简单的 SAT 问题 有 n 个逻辑变量，下面公式（ 1 ）用“ + ”表示或运算符，用“ ’ ”表示非运算符，将与运算符省略了。 SAT = ( x 1 ’+ x 2 ’+ x 3 ’)( x 1 ’+ x 2 + x 3 ’)( x 1 + x 2 ’+ x 3 )( x 1 + x 2 + x 3 ’)( x 1 ’+ x 3 + x 4 ’)( x 1 ’+ x 3 + x 4 )( x 3 ’+ x 4 ’+ x 6 + x 9 ’)( x 3 + x 5 ’+ x 6 ’)( x 3 ’+ x 5 ’+ x 6 + x 10 )( x 3 + x 5 + x 6 + x 10 )( x 6 + x 7 + x 8 ’)( x 6 + x 7 ’+ x 8 )( x 6 ’+ x 7 + x 8 ’)( x 8 ’+ x 9 )( x 8 + x 9 )( x 10 ’) (1) 公式（ 1 ）的逻辑运算式叫合取范式。 合取范式能不能有一组变量值是其结果是 1 （“真”），这就是 SAT 问题。 显然，我们可以将 2 n 个不同的 n 位二进制数带入（ 1 ）右端检验结果，一定可以找到答案，这是穷举法，是 2 n 指数时间的算法。 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
标签: 限位数
