众所周知，判断哈密尔顿回路的存在是一个NP问题，而判断普通回路的存在却是一个P问题。我们对比分析这二个问题，帮助直觉体会NP的本质属性，揭示“多项式时间可验证”的流行NP定义所隐藏的认知错误。

一，Cycle Problem（CP）与Hamiltonian Cycle Problem（HCP）

设G=(V,E)是无向图，V是结点的集合，E是边的集合，记结点数n和边数m：|V|=n，|E|=m。

CP：任给一个无向图，判断是否存在普通回路。

HCP：任给一个无向图，判断是否存在哈密尔顿回路。

这里我们只考虑连通无向图，举二个实例：图G1存在哈密尔顿回路（6 1 2 3 4 5 7 6）；图G2不存在哈密尔顿回路。

二，求解CP

由图论即可判断普通回路的存在性：若m＝n－1，则G是树，不存在回路；若m>=n，则G不是树，存在普通回路。

若普通回路存在，通常可采取深度优先搜索（DFS）算法构造此回路：在搜索的过程中，如果发现正在访问的结点有一条边指向已经访问过的结点，则表示是回路，算法停止搜索。

深度优先搜索算法的复杂度是多项式：O(n+m)。

对于G1和G2，假设每个结点的相邻结点按序号从小到大排列，以结点6作为搜索的起点，深度优先搜索出一条普通回路：1 2 3 1。

三，求解HCP

对于一般的无向图，没有如判断普通回路存在的分析性质，只能采取“猜测＋验证”的搜索方法来判断。

这里依然采取深度优先搜索算法的框架来说明，在搜索的过程中保存正在构造的回路，每次只加还未出现于其中的结点，若没有这样的结点可加，则说明所得是一条回路，若此回路是哈密尔顿回路，则搜索停止，见图G1；若此回路不是哈密尔顿回路，则需回溯到某个可以继续搜索的结点，再重复上述过程。如果寻找不到哈密尔顿回路，则搜索会一直进行下去，见图G2。

这个加了回溯机制的搜索算法，其算法复杂度成为指数型，对应HCP的搜索空间规模。

四，对比HCP与CP

我们可以看到，对于搜索过程中的一个结点序列：v1 v2…vk v1，vi/=vj，通过检查vi与vi+1是否相邻，及根据k<n或k＝n，就可以验证此序列是普通回路还是哈密尔顿回路。但此“多项式时间可验证”是HCP与CP共有的属性，并不能区别HCP与CP，也就是说，当问：HCP与CP有什么不同？不能回答：“多项式时间可验证”。

那么HCP与CP到底有什么不同？表现在“判定问题”的层次：普通回路具有“线性结构”，在实际构造回路之前，就能通过分析性质判断回路的存在。然而，哈密尔顿回路具有“非线性结构”，无分析性质可判断哈密尔顿回路的存在，只能通过实际构造回路来判断：当算法搜索到一条哈密尔顿回路时，回答yes；但是当搜索的结果不是哈密尔顿回路时，不能回答no，需回溯继续搜索。又因HCP的搜索空间规模为指数型，而图灵机的计算能力无法胜任问题规模的指数级增长，故在实时意义下，搜索可能无穷进行下去，永远无法判断该图是否存在哈密尔顿回路，这正是HCP与CP的根本区别，反映的是“确定性”与“不确定性”的本质区别，也是基于NDTM诸NP流行定义最大的认知盲点所在（见从集合论的观点看NP）！

由此可见，“多项式时间可验证”的本质是P，根本无法定义NP，如果坚持用之定义NP，只能导致NP的本质“不确定性”消失，引起对NP认知的混淆和表达的混乱，让NP理论的研究从此失去方向，无法与现在蓬勃发展的人工智能理论衔接。