“P对NP”(P versus NP, P vs NP)问题是当前最重要的数学或理论计算机科学难题之一。其现有的研究与证明方法主要有三大类：对角化diagonalization、电路复杂性circuit complexity、证明复杂性proof complexity。但国际学术界普遍的看法是这些方法都不能得到彻底的结果。一般认为，“不同数学领域的意外结合”、“P或NP新特征的使用”、“新的电路复杂性下界证明方法”以及“对角化的新变形”等是可能获得新结果的途径。

下文缩写：NDTM，non-deterministic Turing machine，非确定型图灵机；DTM，deterministic Turing machine，确定型图灵机;NPC，NP-complete，NP-完全;NPI，NP-Intermediate，不属于P类且不属于NP-完全问题，早期指“人们不知道是属于P类还是属于NP-完全类，还有待于证明其归属”；CH，continuum hypothesis，连续统假设；TSP，traveling salesman problem，旅行推销员问题。

根据1974年Chaitin定理(Gödel第一不完全性定理的信息论形式的具体化)，以及连续统假设CH对Zermelo-Fraenkel集合论公理系统独立性等大量的数学证明实践，本文认为：

(1)“P对NP”问题长期没有公认答案，首先源自该问题的描述出现了某种不确定性。“P对NP”类似希尔伯特第四问题(直线作为两点间最短距离问题，The problem of the straight line as the shortest distance between two points)，描述得太隐晦、太宽泛。

(2)“P对NP”实际上是三个更具体问题的合成：①在NDTM中P等于NP；②在DTM中P不等于NP；③不指定具体的理论计算机模型，则具有独立性。这是对1975年Baker、Gill和Solovay观点“存在不同的计算模型A、B，使得PA=NPA、PB¹NPB分别成立”的进一步细化。

在上述问题描述的明确化后，根据“不同数学领域的意外结合”和“P或NP新特征的使用”来研究“P对NP”，可以得到对该难题的新看法：

(1)由NP定义可知“对于NDTM，PA=NPA”，因此“对于DTM，PB¹NPB”才是研究的重点。这十分类似希尔伯特第四问题，“P对NP”问题描述的不确定性，误导了人们的研究。造成了“P对NP”研究额外的困难性。缺少对DTM和NDTM结构差异的充分使用，是导致“对于DTM，P¹NP”长期缺乏明确结论的原因之一。

(2)目前的以及历史上出现的各种主流研究方法，都集中在P或NP问题类的数量性质研究上。从问题类角度看，由于NPC类、P类只是在DTM上计算“速度”的差异，只是一种“量”的区分，而不像“可计算性”是一种质的区分，这是引起“P对NP”困难性的原因之二。因为证明所采用的“逻辑”，通常是成立、不成立两种明确状态(质)划分的。

(3)“形转化”新思路是将“P对NP”从现在主流的在“数量关系”角度的研究，转化成以“空间形式”角度为主的研究。就是将多项式、指数时间等数量特性，转化为平面图、非平面图等空间、形状特性。

(4)如果能证明对于DTM，P不等于NP，则可以进一步研究无穷版本下的NPI与Cantor原本意义下连续统假设的关系。预计可以得出不接受连续统假设的结论。

下面介绍以此得到的2个具体结果：

(1)尽管在平面图上也可以出现NPC，但大多数NPC出现在非平面图上。不难发现，复杂的TSP可以包含Kuratowski图K5或K3,3，不是平面图。同时一个满二叉树(full binary tree)的高度为可数无穷基数时，会包含K3,3，不是平面图。简言之，非平面图是出现NPC的充分条件。

(2)最小的NDTM就是DTM；一个大的NDTM具有满二叉树(满多叉树)结构，其经过t步计算后的总状态数为2t个。换言之，一个NDTM可以等效为指数界的DTM在同时工作。在这种意义下，NDTM可以看成DTM的幂集。接受Zermelo–Fraenkel集合论公理系统中的“幂集公理Axiom of power set”，即可证明“对于DTM，P¹NP”。

(3)在无穷化版本下，即t取为可数无穷基数a，则DTM只有一个新状态、以及总共经历a个状态；相反，NDTM可以产生2a=c个新状态、以及总共经历a´c=c个状态。即在无穷意义下，“对于DTM，P¹NP”。并且，NPI的存在性，就是Cantor原本意义下的“连续统假设CH”：可数无穷基数a和连续统基数c之间是否存在一个其它的无穷基数。

参考文献：

[1]  THE CLAY MATHEMATICS INSTITUTE. P vs NP Problem [EB/OL]. 

       http://www.claymath.org/millennium/P_vs_NP/.

[2]  COOK S. The importance of the P versus NP question [J]. Journal of the ACM, 2003, 50(1): 27-29.

[3]  SEIFE C. What are the limits of conventional computing? [J]. Science, 2005, 309(5731): 96.

[4]  ALLENDER E. A status report on the P Versus NP question [J]. Advances in Computers, 2009, 77: 117-147.

[5]  HAZEWINKEL M. Encyclopaedia of Mathematics [M]. Dordrecht: Kluwer Academic Publishers, 2001. [DB/OL], http://eom.springer.de/.

[6]  FORTNOW L. The Status of the P versus NP Problem [J]. Communications of the ACM, 2009, 52(9): 78-86.

[7]  CHAITIN G J. Information-theoretic computational complexity [J]. IEEE Transactions on Information Theory, 1974, 20(1): 10-15.

[8]  HARARY F. Graph Theory [M]. Massachusetts: Addison-Wesley, 1969.

[9]  杨正瓴. 从NP结构到超级计算机分类理论[R]. 天津大学百年校庆研究生院学术报告会(一等奖论文)，1995年10月.

[10]  杨正瓴，林孔元. 人类智能模拟的“第2类数学(智能数学)”方法的哲学研究[J]. 哲学研究，1999, (4): 44-50.

[11]  杨正瓴. 密码学与非确定型图灵机[J]. 中国电子科学研究院学报, 2008, 3(6): 558-562.

[12]  杨正瓴. 第二类计算机构想[J]. 中国电子科学研究院学报, 2011, 6(4): 368-374.