算法程序执行时间计算与P=NP问题终结

姜咏江

  对于千禧大奖P与NP问题，我给出了肯定的回答P=NP。为什么？这是因为解答p与np类问题是否相同，只懂得数学知识不行，还必须深刻理解计算机的核心设计方法，理解程序执行的本质，即任何算法程序的执行都是由确定执行时间的机器指令执行累计而成的。懂得了这一点，才会理解任何计算机算法程序能够解决的问题，全都是在所谓多项式时间内完成的，而且所有的结果都是有限的。真正懂得计算机设计的人都能够懂得，无限多的结果是不能够通过计算机计算出来的。这就是说不论何种形式的算法程序，最终都要转化成所谓多项式时间复杂度的机器指令程序执行完成。我相信，理解了这种计算机（包括图灵机）的程序执行基本方式，就不难理p与np的问题了。

1.             程序执行时间计算公式

  计算机任何程序执行都是通过相应的机器指令执行来完成的。考虑到不失一般性，可以假定机器指令周期相同。那么对于一个程序来说，循环结构的层数和每层循环的次数，及循环体内的执行指令数是决定程序执行时间的因素。为了说明问题简单，我们假设每层循环的次数都是n，那么k层循环结构中指令重复执行总数就可以用下式计算：

f(n,k) = a₀n⁰+a₁n¹+a₂n²+...+ a_k-1n^k-1+a_kn^k =    

               （1）

其中a_i为第i层执行的指令数。

  考虑到程序由j个子程序构成，那么（1）式可以表示成  

              （j）

  如果程序含有有限次子程序嵌套，只要将调用语句换成相应的子程序，就可以转化为非嵌套形式，自然可以用公式（j）计算程序执行时间了。

2.             算法程序执行都是多项式时间

  不论在计算机上执行的任何程序，只要要能够得到结果，则n与k都必须是确定的自然数。既然k是自然数，就总可以认定（j）式是一个多项式，因而总可以认定任何可以求出结果的算法程序执行时间总为（j）式的多项式时间。

3.             p与np问题

  人们认可的p与np问题是如下定义的：

  复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。

  问题的焦点是P=NP？

  我们先来解释P类问题为什么会提出来。

  我们暂且将图灵机就理解成现在的计算机，那么要搞清计算机解决的问题是什么。简单地说，问题是由条件和结果两部分组成的，解决问题往往是从条件出发寻求结果的过程，在计算机上实现的方法是通过程序执行完成。程序的设计方法称为算法，即使是同一个问题，也可能有不同的算法，因而书写的程序往往是不相同的。同一个问题的不同算法程序执行时间有长有短，故而人们提出了研究算法效率的时间复杂度，进而来确定程序设计当中算法的优劣。在算法时间复杂度研究中，多数人错误地认为多项式形式的算法程序执行时间会最短，因而提出了所谓p类问题。

4.             计算机能够解决的问题都是p类问题

  通过程序执行时间的计算，我们可以断定，靠程序设计的组织形式来判定程序执行时间的长短并不准确，这其中起着决定性作用是数据的结构和数据量。由公式（j）我们立刻可以知道计算机能够计算出结果的问题都是p类问题。因而提出p类问题的实际意义并不很大。实际决定程序执行时间长短的是程序循环层次数k和指令在循环体内的执行次数n和不同种指令数a。任何在计算机上能够解决的问题，循环层次数k和指令重复执行数n最高都是一个确定的自然数，不可能出现无穷大，因为这样计算机无法计算出问题结果。

5.             计算机解决问题结果都可顺序查询

  计算机可以求出的问题结果都是有限的，因而对结果的查询都可顺序进行。因为问题结果为有限多个，因而总可以对任意的猜测结果，通过顺序查询来回答yes/no的问题。顺序查询的时间复杂度为O(n)（为说明问题简单，在此借用一下这类符号），即是所谓的多项式时间查询。如此我们可以得出结论：任何计算机算法程序执行的结果都可以用多项式时间复杂度查询。

6.             结论及其它

  从4和5我们不难知道P类问题集合与NP类问题的集合是一个，即P=NP。

  许多学者的疑问是：P与NP的问题如此简单，“为什么还有那么多的学者在此问题上绞尽脑汁？为什么P versus NP会演变成世界难题？”

  这个问题说起来，应该归结到数学与计算机科学研究的不同之处。首先要知道除非专门讨论时间，各种数学方法并不带有“时间要素”。数学并不要象计算机那样随时都要考虑时间要素。举例来说，考察两个变量x、y是否相等，数学在推演中只要得出x=y或x≠y的结果就行，而计算机程序执行却要考察x、y的值何时相等与何时不等，因为只有在恰当的时间点上，计算机程序执行才会得出正确的结果。

  搞数学而对计算机不甚透彻理解的人，可以设计计算机程序，而且某些算法程序会设计得很完美。但他们思考问题的方式并不带有时间要素，即使有，或者也是将他们设计的各种算法语句就替代了计算机执行的真实时间。这样一来就可能抽象出“多项式时间复杂度”这类，以算法中具有代表性的“最高项”讨论时间的做法，实际上这已经脱离了计算机本质的时间特性。

  至于说到P与NP是否相等的证明，我想就不必费时间了吧。我们知道概念是逻辑证明的基础，如果我们对“多项式时间复杂度”这类概念含糊其辞，还怎么去证明呢？从本文的（j）公式已经能够清楚地理解，无论什么样的算法程序执行的时间计算，都可以理解成多项式时间；而计算机算法程序能够处理的问题总是有限的，因而都可以用顺序的查询方式获得是与否的答案，那么还能说P versus NP是世界难题吗？

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

http://blog.sciencenet.cn/blog-340399-861142.html

2015-05-04