至此，针对流行的NP定义：NP＝Nondeterministic Polynomial time，我们提出了新的NP定义：NP＝Nondeterministic Problem。

这里，我们用Sisper书（Introduction to the Theory of Computation）中的二个实例来分析和对比这二种定义。

一，二种NP定义

1，NP＝Nondeterministic Polynomial time（不确定性多项式时间）

此定义基于“Nondeterministic Turing machine（NDTM）”，这里的“不确定性”指NDTM在计算中“多选择”意义上的“可选择性”。

如文献及我们的博文分析，于“算法”的层次，NDTM与DTM等价，故有将NP定义为“多项式时间可验证的问题”一说。

2，NP＝Nondeterministic Problem（不确定性问题）

此定义指“可计算性”意义上的“不确定性”，此“不确定性”源于问题本身的非线性结构，表现在算法策略上就是“判断的不确定性”，故此“不确定性”与图灵时代提出的“判定问题（decision problem）”密切相关。

图灵不得已用“神喻机”，也就是我们称之的“非图灵机（Non Turing machine，NTM）”来表达此“不确定性”，正因为这种源于问题本身的“不确定性”，故称NP为“不确定性问题”，具有阐释的意义。

二，二个实例（见博文：参详P与NP的二个实例，http://blog.sciencenet.cn/blog-2322490-878672.html）

针对一个“计算问题”，即用算法求解的问题，一般可从“问题”和“算法”二个层次进行表述：

1，普通路径问题（The PATH problem）

－“问题”层次：任给一个有向图G及二个结点s和t，判断G中是否存在一条从s到t的路径？

－“算法”层次：任给一个有向图G及二个结点s和t，求解G中一条从s到t的路径。

2，哈密顿路径问题（The HAMPATH problem）

－“问题”层次：任给一个有向图G及二个结点s和t，判断G中是否存在一条从s到t且遍历G的所有结点的路径（哈密顿路径）？

－“算法”层次：任给一个有向图G及二个结点s和t，求解G中一条从s到t且遍历G的所有结点的路径（哈密顿路径）。

“普通路径问题”是P问题；“哈密顿路径问题”是NP问题。

三，分析和对比二种NP定义

1，NP＝Nondeterministic Polynomial time

求解“普通路径问题”和“哈密顿路径问题”的算法，都是基于搜索的算法，从博文“参详P与NP的二个实例”所举的二个算法示意图看，都可表达为“搜索树”，也就是说，构造从s到t的普通路径和哈密顿路径的计算过程中，都存在着“多选择”的“可选择性”。

是故，NDTM的“可选择性”，不足以把“哈密顿路径问题”与“普通路径问题”区别开，换句话说，因“多项式时间可验证性”，“哈密顿路径问题”与“普通路径问题”都成了NP问题，依流行的说法，就是：P ⊆ N P 。这也就是我们所说的，流行NP定义暗中肯定了NP＝P，致使“不确定性”从NP中消失，“NP＝P？”遂成悖论！

2，NP＝Nondeterministic Problem

从“问题”和“算法”的关系中，我们可以看到二者的区别：

于“普通路径问题”，只要找到一条从结点s到结点t的路径，就可肯定是所求的解，比如，s＝1，t＝8，1-3-7-8，换句话说，在构造从s到t的普通路径的过程中所作的判断，具有“确定性”的意义。

然而，于“哈密顿路径问题”，找到一条从结点s到结点t的路径，并不能肯定是所求的解，比如，s＝1，t＝8，1-3-7-8，而所求是否为的解，要等到构造路径的过程结束时才能知道，换句话说，在构造从s到t的哈密顿路径的过程中所作的判断，具有“不确定性”的意义。

正是在此意义上，新NP定义表达的“不确定性”将“哈密顿路径问题”与“普通路径问题”区分开了，而这正是最初提出NP概念的初衷！