P versus NP问题的认知盲点

姜咏江

The P versusNP problem is a major unsolved problem incomputer science. It asks whether every problem whose solution can bequickly verified (technically, verified in polynomialtime) can also be solved quickly (again, in polynomial time).

       这个问题长期不能够解决的原因，是因为认知上存在盲点。第一，因为这是一个计算机科学的问题，因而与计算机的结构直接相关。忽略了计算机本身结构的变化对该问题的影响，就会陷入似是而非的状态。第二，数学方法是无法分析并行处理状态量的变化，因而用数学方法不能够分析串并行的相互关系。

例如，n个数的子集共有2ⁿ个。每个数用一个位置信息来表示，那么所有的子集表示都是一个SAT问题的子句，问题就可以转化为SAT问题求解。许多NP问题都可以归约为SAT问题。如果SAT问题能够用计算机在硬件资源充沛的前提下，能够在多项式时间求出全部解，那么就证明了P=NP。

       本人前文提到的子句标志消去法，如果用数学方法去寻找可能解集中包含一个子句的可能解，就需要逐一查找每个可能解的子句位置是否就是这个子句，这当然要比较2ⁿ次。这就是所说的关于n的指数时间。如果计算机具有一次就可以将全部可能解比较完成，那对SAT问题求解就是关于子句数量m的线性时间复杂度！实际上这是快得不能再快的设计方法了。

       现行结构的计算机系统，都是顺序结构思想下的产物，同纯数学方法一样，不可能找到一次多项式时间算法，因而不可能在短时间内完成求解。而硬件并行数据处理就可以在线性时间完成求解。

       尽管人们制造了超级并行计算机系统，但那仍然是串行处理问题的计算机与计算机组合，这需要将数据拆分或大量复制，远远比不上可以并行求出SAT问题解的一个处理器计算机的效率。

       毫不客气地预测，在现今集成电路微化的时代，一台笔记本电脑的并行处理器系统，就可以在SAT一类问题的处理上，赛过一列火车式的“超级计算机”。

   欢迎有不同观点的朋友拍砖头。

2018-1-23