P和NP指二个问题类。NP存在着二个流行定义（见Sipser的书“Introduction to the Theory of Computation”，Section 7.3［1］）：

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

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

于博文中（http://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&id=874183），我们通过分析二个定义中涉及到二个内涵完全不同的“非确定型图灵机”，揭示了NP二个定义不等价。

这里，我们试举Sipser书中P和NP问题类中的二个实例，供大家进一步参详NP二个定义的区别。

Sipser的书作为算法理论的教材和研究资料，被学术界广泛引用。这里，我们只负解释原文的责任。

一，二个实例

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

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

求解：基于广度优先搜索的多项式时间算法。

于是，“普通路径问题”是一个P问题。

例如，图1中给出有8个结点的图G，s＝1，t＝8。图2给出广度优先搜索树，可得路径：1-3-7-8。

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

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

求解：或者逐条穷举所有可能的路径，验证其是否为从s到t的哈密顿路径；或者采用某种策略生成一条可能的路径，验证其是否为从s到t的哈密顿路径。

但这些算法在多项式时间内都无法判定是否存在一条哈密顿路径，故解决此问题的多项式时间算法的存在成为了“问题”，于是，“哈密顿路径问题”是一个NP问题。

同样于图1中的G，图3给出穷举搜索树，可得哈密顿路径：1－3－5－4－2－6－7－8。

二，参详NP二个定义

就NP二个定义而言，于基于验证的定义，指存在“确定型图灵机（算法）”在多项式时间验证一个问题的“解的真假”；于基于判定的定义，指基于“神喻机”的“非确定型图灵机”在多项式时间内可判断一个问题的“解的存在”。

于是，我们可以思考：以“普通路径问题”和“哈密顿路径问题”为例，NP二个定义会导致什么样的P与NP的关系？

参考文献

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

附录：为方便大家的阅读，我们将Sisper书中与二个实例相关的段落摘抄如下：

p.263

THE CLASS P

The first problem concerns directed graphs. A directed graph G contains nodes s and t, as shown in the following figure (FIGURE 7.13). The PATH problem is to determine whether a directed path exists from s to t.

The PATH problem : Is there a path from s to t?

Theorem 7.14 : PATH is in P.

PROOF IDEA

We prove this theorem by presenting a polynomial time algorithm that decides PATH. Before describing that algorithm, let's observe that a brute-force algorithm for this problem isn't fast enough.

A brute-force algorithm for PATH proceeds by examining all potential paths in G and determining whether any is a directed path from s to t. A potential path is a sequence of nodes in G having a length at most m, where m is the number of nodes in G. (If any directed path exists from s to t, one having a length of at most m exists because repeating a node never is necessary.) But the number of such potential paths is roughly M^M, which is exponential in the number of nodes in G. Therefore this brute-force algorithm uses exponential time.

To get a polynomial time algorithm for PATH we must do something that avoids brute force. One way is to use a graph-searching method such as breadth-first search. Here, we successively mark all nodes in G that are reachable from s by directed paths of length 1, then 2, then 3, through m. Bounding the running time of this strategy by a polynomial is easy.

P.268

THE CLASS NP

A Hamiltonian path in a directed graph G is a directed path that goes through each node exactly once. We consider the problem of testing whether a directed graph contains a Hamiltonian path connecting two specified nodes, as shown in the following figure (FIGURE 7.17).

We can easily obtain an exponential time algorithm for the HAMPATH problem by modifying the brute-force algorithm for PATH given in Theorem 7.14. We need only add a check to verify that the potential path is Hamiltonian. No one knows whether HAMPATH is solvable in polynomial time.

The HAMPATH problem does have a feature called polynomial verifiability that is important for understanding its complexity. Even though we don't know of a fast (i.e. polynomial time) way to determine whether a graph contains a Hamiltonian path, if such a path were discovered somehow (perhaps using the exponential time algorithm), we could easily convince someone else of its existence, simply by presenting it. In other words, verifying the existence of a Hamiltonian path may be much easier than determining its existence.