在计算复杂性理论中，NP是用“非确定型图灵机（nondeterministic Turing machine，NDTM）”来定义的，从“语言”的角度，存在着二个流行的定义（见[1] : Michael Sipser, Introduction to the Theory of Computation, Section 7.3）：

1，基于验证的定义：NP是“确定型图灵机”在多项式时间内可验证的语言类；

2，基于判定的定义：NP是“非确定型图灵机”在多项式时间内可接受的语言类。

实际上，这二个定义涉及到二个内涵完全不同的NDTM，但是学术界未能认识到这点，将这二个NDTM混淆，得出NP二个定义等价，导致了对NP的认知偏差。

这里，我们试分析NDTM的二个不同所指，使得进一步追究NDTM成为可能。

一，验证定义中的NDTM

验证定义中的NDTM，是学术界公认、源自“非确定型自动机”的“非确定型图灵机”［1］。

其定义为：与“确定型图灵机（deterministic Turing machine，DTM）”相对，在计算的每一时刻，根据当前状态和读写头所读的符号，机器的下一个状态存在“多选择”。

其计算如下：对于表达成字符串w的一个问题的例子，在多项式时间内，猜测一个“证书 c”，然后在多项式时间内验证c，若验证的结果为真，M接受w；但若验证的结果为假，M并不能真正拒绝w，因为c仅是一个“猜测解”。于是，此NDTM不能在多项式时间内接受语言！

因上述NDTM的计算在多项式时间内完成，故可用DTM来模拟，如Sipser书中Theorem 3.16所说，“Every nondeterministic Turing machine has an equivalent deterministic Turing machine”［1］，遂有基于验证的NP定义。正是在这种意义上，基于验证定义中的NDTM本质上只是TM。

二，判定定义中的NDTM

判定定义中的NDTM，最初出现在Cook那篇奠定计算复杂性基础的论文《The Complexity of Theorem Proving Procedures》（1971年）中：

Theorem 1 If a set S of strings is accepted by some nondeterministic Turing machine within polynomial time, then S is P-reducible to {DNF tautologies}.

这里的“a set S of strings is accepted by some nondeterministic Turing machine ”  以后被作为了NP问题的原始定义，即基于判定的NP定义，被学术界广泛接受［2］，解释为NDTM在多项式时间内接受某个语言，这意味着此NDTM可以：

1，在多项式时间内判断一个具体的NP问题实例是否有解；

2，在多项式时间内为此问题求得“精确解”。

那么，具有这样能力的只能是“神喻机（Oracle）”，而不是验证定义中的NDTM了！

换句话说，此NDTM非彼NDTM也，实指“神喻机”！对此议题，我们已在文章“What is Cook’s theorem?”作了详细的论证，故不在此深入。

三，NDTM概念中的“不确定性”内涵

由此可见，NP二个定义中的NDTM术语未变，所指却完全不同：

于验证定义，NDTM ＝ 确定型图灵机；

于判定定义，NDTM ＝ 神喻机。

这里的“确定型图灵机”与“神喻机”在NP问题形成的学术史中处于完全不同的层次，NP二个定义中的二个NDTM具有不同的意义，它们的混淆正是NP问题中的“雾霾”。

然而，无论是指“神喻机”意义的NDTM，还是指“确定型图灵机”意义的NDTM，在现有的两个NP定义中，二者其实都只有“确定性”的意义，并无真正的“不确定性”的本质。正是在这种意义上，我们认为：“不确定性”从流行的NP定义中消失了！

在现有的NP问题概念中厘清这些混乱，在NP理论中建立真正的“不确定性”概念，是我们现有研究工作的主要目的。

参考文献

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

［2］Garey Michael R., David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and company (1979).