Cook在介绍千禧年难题“The P versus NP Problem”［1］时说：

－The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is also accepted by some (deterministic) algorithm in polynomial time.

这就是NP完备理论中P和NP的形式化定义：P是图灵机（TM）接受的语言类；NP不确定性图灵机（NDTM）接受的语言类。

对于这种定义，Garey、Johnson在其书“Computer and intractability”［2］中简单解释到（p.18,19, 20）：

As a matter of convenience, the theory of NP-completeness is designed to be applied only to decision problems.

The reason for the restriction to decision problem is that they have a very natural, formal counterpart, which is a suitable object to study in a mathematically precise theory of computation. This counterpart is called a "language" and is defined in the following way.

其实之所以将NP作为“decision problem”研究，并非简单的“As a matter of convenience（为方便起见）”，而是有深刻的哲学背景，就形式化方法研究而言，可借助于称之为“language（语言）”的概念，将“decision problem”与集合论产生联系。

本文与博文认知云里说NP互补，从集合论的角度再说NP，进一步揭示NP的流行定义中“不确定性”的消失，阐释NP的本质。

一，集合、问题与问题求解

集合论被认为是近代数学的基础，指以“集合”为基本概念，形式化地定义数学对象加以研究。集合者，将一些对象汇集而成的整体，构成集合的对象称为“元素”，元素与集合的“所属关系”定义一个集合。

于是，从集合论的观点，可以形式化定义“问题”及“问题求解”。“问题”指“所有实例的集合”，“语言”指“所有存在解的实例的集合”，“问题求解”指以“算法”为工具判断任何一个实例是否属于“语言”这个集合。“算法”被形式化表达为“图灵机”，“问题”则被表达为“判定问题（decision problem）”。

比如，SAT问题指所有的合取范式的集合，SAT问题的“语言”指所有可满足的合取范式的集合，记作：SAT＝｛所有可满足的合取范式｝。求解SAT问题就是指用算法来判断任何一个合取范式w是否属于SAT，若w属于SAT，则w是可满足；否则w是不可满足的。

二，图灵机接受的语言，P与NP

从集合的角度，如果图灵机能判断任何一个实例是否有“解”，就意味着定义了“语言”这个集合，也就是求解了对应的“问题”，在此意义下，称此问题是“图灵机接受的语言”，由此来定义P和NP。

图灵机是通过“计算”来“判断”的，即任给一个实例w，若图灵机计算得到一个解，则回答“yes”，说明w有解，图灵机“接受”w；若图灵机计算得不到解，则回答“no”，说明w无解，图灵机“拒绝”w。

显然P问题是图灵机接受的语言，即可确定性求解的问题，计算复杂性理论中由“多项式时间”（Polynomial time，P）来表达。

对于NP问题，图灵机的计算实际上是“猜测＋验证”：任给一个实例w，图灵机只能在多项式时间“猜测”出一个候选解c，并能在多项式时间“验证”c，若验证回答“yes”，则c是w的“解”，图灵机“接受”w。然而这里的关键是，若验证回答“no”，只能说明c不是w的“解”，却不能由此判断w没有“解”，也就是说，w可能有解也可能无解，故“no”的判断是“不确定的”，因此图灵机还不能“拒绝”w，需要继续搜索，这样就又回到了原问题，如此图灵机可能永远不停机，就是说，真正的NP是下面图示中下方那个无穷追索，永不返回的“no”的路径。所以，图灵机对NP问题的判断具有“不确定性”，即“NP不是图灵机接受的语言”，也就是说，NP是“不可判定（undecidable）”的，这才是NP的本质！

然而，在NP完备理论中，却把代表NP的本质的“不确定性”的判断“no”与“确定性”的“拒绝”混淆了［2］：

The computation ceases when and if the finite state control enters one of the two halt states (either qY or qN ) and is said to be an accepting computation if it halts in state qY . All other computations, halting or not, are classed together simply as non-accepting computations.

然后将上述错误解释判断“no”的图灵机的计算模式，谓之“不确定性图灵机（NonDeterministic Turing Machine, NDTM）”，将NP问题定义为“不确定性图灵机接受的语言”。

三，NP的流行定义与“不确定性”的消失

由此，NP的流行定义对“NP”的权威解释就是“不确定性多项式时间”（Nondeterministic Polynomial time），指存在多个“多项式时间”因而具有“多选择”，但这等于说，（事先）肯定（至少一个）多项式时间存在，所以NDTM只不过是在多项式时间内搜索得到一个确定性的回答，也就是说，NDTM与TM等价［3］，由此得出“NP是可计算的，可判定的”，这正是现有的NDTM这个概念的实质。

进一步，又把“解的确定性验证”作为NP的标准定义，即所谓的“可验证定义”，是有NP二个定义等价之说。然而从集合的角度，可以清楚看到，“解的确定性验证”是典型的P问题！

所以，无论是用“不确定性多项式时间的多选择”还是“解的确定性验证”来定义NP，都是暗中肯定NP＝P，源于回避上述图灵机判断的“不确定性”，其结果是NP的“不确定性”本质从现有的NP完备理论中彻底消失，“P versus NP”遂成悖论，是有千禧年难题（《紐約客》科普“P versus NP”（MAY 2, 2013）），。。。

四，“不确定性”与Entscheidungsproblem

我们的NP理论工作就是致力于寻找消失了的NP本质－“不确定性”。实际上，“不确定性”与图灵1936年论文对“Entscheidungsproblem（判定问题）”的研究密切相关，这也就是我们为什么要追本溯源重新解读图灵1936年的论文的根本原因。

参考文献：

［1］Stephen Cook,ThePversusNPProblem.ClayMathematicsInstitute.

http://www.claymath.org/millennium/P vs NP/pvsnp.pdf.

［2］Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory

of NP-Completeness. W. H. Freeman and company (1979).  

［3］Michael Sipser, Introduction to the Theory of Computation, Second Edition. International. Edition (2006).