在计算复杂性理论中，NP是基于“不确定性图灵机（nondeterministic Turing machine，NDTM）”来定义的，指NP是NDTM多项式时间可求解的问题。于“求解”的定义，又可表达为基于“判定”的定义，指NP是NDTM多项式时间可接受的语言（即NDTM多项式时间可判定解的存在），此定义源于Cook定理，其中的NDTM具有“神喻机（Oracle）”的性质，因为只有具有“神喻”性质的东西才能在“理论上”于多项式时间内对NP问题求解或判断解的存在，而“神喻机”是图灵为表达与“图灵机”相对的一种机制不得已的说法，被Cook借用来表达“NDTM＝Oracle＋TM”［1］（更详细的解读可见英语文章: Interpretation of NDTM in the definition of NP）。

NP的流行定义指NP是图灵机（Turing machine，TM）多项式时间可验证的问题，学术界一致认为这二个定义等价，是有“验证”定义取代“求解”定义，成为了NP的标准定义：

－The two definitions of NP as the class of problems solvable by a nondeterministic Turing machine in polynomial time and the class of problems verifiable by a deterministic Turing machine in polynomial time are equivalent. The proof is described by many textbooks, for example Sipser’s Introduction to the Theory of Computation, section 7.3  （http://en.wikipedia.org/wiki/NP (complexity) ）。

于博文（解读NDTM的概念偷换－NP定义中二个不同的NDTM），我们已经揭示了深藏在NDTM中的“概念偷换”，这里通过解读Sipser书中关于NP二个定义等价的证明［2］，进一步分析这一令人难以察觉的逻辑认知错误。

一，证明的原文

Theorem 7.20 A language is in NP iff it is decided by some nondeterministic polynomial time Turing machine.

Proof idea:

We show how to convert a polynomial time verifier to an equivalent polynomial time NDTM and vice versa. The NDTM simulates the verifier by guessing the certificate. The verifier simulates the NDTM by using the accepting branch as  the certificate.

Proof: From the forward direction of this theorem, let A in NP and show that A is decided by a polynomial time NDTM N. Let V be the polynomial time verifier for A that exists by the definition of NP. Assume that V is a TM that runs in time n^k and construct N as follows.

N = On input w of length n:

1. Nondeterministically select string c of length at most n^k.

2. Run V on input <w,c>.

3. If V accepts, accepts; otherwise, reject.

To prove the other direction of the theorem, assume that A is decided by a polynomial time NDTM N and construct a polynomial time verifier V as follows:

V = On input < w, c >, where w and c are strings:

1. Simulate N on input w, treating each symbol of c as a description of nondeterministic choice to make at each step.

2. If this branch of N’s computation accepts, accept; otherwise, reject.

二，证明的译文

定理7.20：如果一个语言在NP中，当且仅当此语言由某个不确定性图灵机在多项式时间判定。

证明思路：

我们展示如何将多项式时间验证器转换为等价的多项式时间NDTM，反之亦然。 NDTM通过猜测证书来模拟验证器，验证器通过使用接受的分支作为证书来模拟NDTM。

证明：

从这个定理的正向看，令A在NP中，证明A可由多项式时间NDTM N判定。令V是A的多项式时间验证器，由NP的定义可知V存在。假设V是在时间n^k内运行的TM，构造N如下。

N =“输入w，其长度为n：

1，不确定性地选择长度至多为n^k的字符串c。

2，在输入<w，c>上运行V。

3，如果V接受c，则N接受w；否则，N拒绝w。

为了证明定理的另一个方向，假设A由多项式时间NDTM N判定，构造多项式时间验证器V如下：

V =“输入 <w，c>，其中w和c是字符串：

1，在输入w上模拟N，处理c的每个符号，c的每个符号是在每个步骤进行的不确定性选择的描述。

2，如果N的这个计算分支接受w，则V接受c；否则，V拒绝c。

三，解读证明

此证明是建立在将验证器V对实例w的一个证书c的“验证”等价于NDTM N接受实例w的“判定”的基础上的：

－正向证明中：如果V接受c，则N接受w；否则，N拒绝w；

－反向证明中：如果N的这个计算分支接受w，则V接受c；否则，V拒绝c。

我们来分析这个基础是否成立。实际上，只有当NDTM指“Oracle＋DTM”时，“验证”与“判定”才能等价，因为在这种情况下，验证器V所验证的就是神喻机得出的结果，验证与判定当然是一致的。

然而，神喻机只是一个思想概念，于现实中并不存在，所以在实际证明中“神喻机”已经被“猜测模块”代替了，也就是说，证明中的NDTM已不再是“Oracle＋TM”，而是“猜测模块＋验证模块”。Sipser举例NP问题“哈密尔顿路径（HAMPATH）”说明这样的NDTM：

The following is a nondeterministic Turing machine (NDTM) that decides the HAMPATH problem in nondeterministic polynomial time. Recall that in Definition 7.9 we defined the time of a nondeterministic machine to be the time used by the longest computation branch.

N = « On input <G, s, t>, where G is a directed graph with nodes s and t:

1. Write a list of m numbers, p1, …, pm, where m is the number of nodes in G. Each number in the list is nondeterministically selected to be between 1 and m.

2. Check for repetitions in the list. If any are found, reject.

3. Check whether s=p1 and t=pm. If either fail, reject.

4. For each i between 1 and m-1, check whether (pi, pi+1) is an edge of G. If any are not, reject. Otherwise, all tests have been passed, so accept. »

To analyze this algorithm and verify that is runs in nondeterministic polynomial time, we examine each of its stages. In stage 1, the nondeterministic selection clearly runs in polynomial time. In stage 2 and 3, each part is a simple check, so together they run in polynomial time. Finally, stage 4 also clearly runs in polynomial time. Thus this algorithm runs in nondeterministic polynomial time.

让我们来分析“猜测模块＋验证模块”的NDTM对于实例<G，s，t>的判定：当p1，...，pm被验证是哈密尔顿路径时，对应的NDTM N就“接受”实例<G，s，t>，即判定实例<G，s，t>有解；然而当p1，...，pm被验证不是哈密尔顿路径时，NDTM N既不能判定实例<G，s，t>无解，也不能判定实例<G，s，t>有解，因为p1，...，pm只是一个猜测（nondeterministically selected）而非神喻机超验的结果，在此意义下，NDTM N的“拒绝”没有意义，对比“Oracle＋DTM”的NDTM对实例<G，s，t>的“确定性”判定，NDTM N对实例<G，s，t>的判定是“不确定性”的，故“验证”与“判定”不一致。所以，无论是基于“神喻机”还是“图灵机”的NP定义都不成立，而“NP二个定义等价”就成了一个伪命题！

于是，若坚持NP的二个定义，实际上就是默许NDTM的“概念偷换”，其后果是将图灵机的“确定性的验证”偷换成神喻机的“超验的判定”，然后去替代图灵机对NP的“不确定性的判定”，从而造成“NP的不确定性消失”，演变为笼罩在“P versus NP”千禧年难题上的不散的认知雾霾，。。。

＊＊＊＊＊＊

维基简介Sipser的书：

Introduction to the Theory of Computation (ISBN 0-534-95097-3) is a standard textbook in theoretical computer science, written by Michael Sipser and first published by PWS Publishing in 1997.

Michael Fredric Sipser (born September 17, 1954) is a theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of Applied Mathematics and Dean of Science at the Massachusetts Institute of Technology.

附此书Section 7.3的原文和译文：

Section 7.3 ：The class NP

As we observed in Section 7.2, we can avoid brute-force search in many problems and obtain polynomial time solution. However, attempts to avoid brute force in certain other problems, including many interesting and useful ones, haven’t been successful, and polynomial time algorithms that solve them aren’t known to exist.

Why have we been unsuccessful in finding polynomial time algorithms for these problems? We don’t know the answer to this important question. Perhaps these problems have, as yet undiscovered, polynomial time algorithms that rest on unknown principles. Or possible some of these problems simply cannot be solved in polynomial time. They may be intrinsically difficult.

第7.3节：NP类

正如在7.2节中所看到的，我们可以在许多问题中避免暴力搜索，获得多项式时间解决。但是，在某些其它问题中，包括许多有趣而有用的问题，避免暴力搜索的努力还没有成功，解决这些问题的多项式时间算法还没有找到。

为什么对这些问题寻找多项式时间算法还没有取得成功呢？我们不知道对这个重要问题的答案是什么。可能这些问题具有基于未知理由的多项式时间算法存在，只是至今还没有被发现，或者它们中某些问题就是不能在多项式时间内解决，它们可能是固有困难的。

DEFINITION 7.18

A verifier for a language A is an algorithm V, where

- A = {w I V accepts <w, c> dor some string c}.

- We measure the time of a verifier only in terms of the length of w, so a polynomial time verifier runs in polynomial time in the length of w. A langage A is polynomial verifiable if it has a polynomial time verifier.

定义7.18

语言A的“验证机”是一个算法V，这里

A = {w I 对某个字符串c， V接受 <w, c> }.

我们用w的长度来度量验证机的时间，所以多项式时间验证机在w的多项式时间内运行。一个语言A是多项式时间可验证的，如果它有个多项式时间验证机。

DEFINITION 7.19

NP is the class of languages that have polynomial time verifiers.

The term NP comes from nondeterministic polynomial time and is derived from an alternative characterization by using nondeterministic polynomial time Turing machine. Problems in NP are sometimes called NP-problems.

定义7.19

NP是具有多项式时间验证机的语言类。

术语NP来自不确定性多项式时间，来自于使用不确定性图灵机的另一特征。NP类的问题有时称作NP问题。

The following is a nondeterministic Turing machine (NDTM) that decides the HAMPATH problem in nondeterministic polynomial time. Recall that in Definition 7.9 we defined the time of a nondeterministic machine to be the time used by the longest computation branch.

以下是一个不确定性图灵机（NDTM），用于在不确定性多项式时间内判定HAMPATH问题。 回想在定义7.9（注1）中，我们将不确定性机器的时间定义为最长计算分支所使用的时间。

N1 = « On input <G, s, t>, where G is a directed graph with nodes s and t:

1. Write a list of m numbers, p1, …, pm, where m is the number of nodes in G. Each number in the list is nondeterministically selected to be between 1 and m.

2. Check for repetitions in the list. If any are found, reject.

3. Check whether s=p1 and t=pm. If either fail, reject.

4. For each i between 1 and m-1, check whether (pi, pi+1) is an edge of G. If any are not, reject. Otherwise, all tests have been passed, so accept. »

N1 = « 输入 <G，s，t>，其中G是有向图，s和t是结点：

1，写一个有m个数字p1，...，pm的表，其中m是G中的结点数。表中的每个数字是在1和m之间不确定性地选择所得。

2，检查列表中结点的重复，如果发现任何有重复，则拒绝。

3，检查是否s = p1和t = pm，如果不是，则拒绝。

4，对于1和m-1之间的每个i，检查（pi，pi + 1）是否是G的边。如果不是，则拒绝。 否则，所有检查都已通过，则接受。 »

To analyze this algorithm and verify that is runs in nondeterministic polynomial time, we examine each of its stages. In stage 1, the nondeterministic selection clearly runs in polynomial time. In stage 2 and 3, each part is a simple check, so together they run in polynomial time. Finally, stage 4 also clearly runs in polynomial time. Thus this algorithm runs in nondeterministic polynomial time.

为了分析这个算法和验证是否在不确定性多项式时间运行，我们检查每个阶段。 在阶段1中，不确定性地选择很清楚是在多项式时间内运行的。 在阶段2和3中，每个部分是简单的检查，因此它们一起是在多项式时间内运行的。 最后，阶段4也很清楚是在多项式时间内运行的。 于是，该算法在不确定性多项式时间内运行。

Theorem 7.20 ： A language is in NP iff it is decided by some nondeterministic polynomial time Turing machine.

定理7.20：如果一个语言在NP中，当且仅当此语言由某个不确定性多项式时间图灵机判定。

Proof idea:

We show how to convert a polynomial time verifier to an equivalent polynomial time NDTM and vice versa. The NTM simulates the verifier by guessing the certificate. The verifier simulates the NDTM by using the accepting branch as  the certificate.

证明思路：

我们展示如何将多项式时间验证器转换为等价的多项式时间NDTM，反之亦然。 NDTM通过猜测证书来模拟验证器，验证器通过使用接受的分支作为证书来模拟NDTM。

Proof:

From the forward direction of this theorem, let A in NP and show that A is decided by a polynomial time NDTM N. Let V be the polynomial time verifier for A that exists by the definition of NP. Assume that V is a TM that runs in time n^k and construct N as follows.

证明：

从这个定理的正向看，令A在NP中，证明A由多项式时间NDTM N判定。令V是A的多项式时间验证器，由NP的定义可知V存在。假设V是在时间n^k内运行的TM，构造N如下。

N = "On input w of length n:

1. Nondeterministically select string c of length at most n^k.

2. Run V on input <w, c>.

3. If V accepts, accepts; otherwise, reject.

N =“输入w，其长度为n：

1，不确定性地选择长度至多为n^k的字符串c。

2，在输入<w，c>上运行V。

3，如果V接受，则接受；否则，拒绝。

To prove the other direction of the theorem, assume that A is decided by a polynomial time NDTM N and construct a polynomial time verifier V as follows:

为了证明定理的另一个方向，假设A由多项式时间NDTM N判定，构造多项式时间验证器V如下：

V = "On input <w,c>, where w and c are strings:

1. Simulate N on input w, treating each symbol of c as a description of nondeterministic choice to make at each step.

2. If this branch of N's computation accepts, accept; otherwise, reject.

V =“输入 <w，c>，其中w和c是字符串：

1，在输入w上模拟N，处理c的每个符号，c的每个符号是在每个步骤进行的不确定性选择的描述。

2，如果N的这个计算分支接受，接受；否则，拒绝。

注1：

Nondeterministic Turing Machine (p.152)

At any point in a computation the machine may proceed according to several possibilities.

The computation of a nondeterministic Turing machine is a tree whose branches correspond to different possibilities for the machine. If some branch of the computation leads to the accept state, the machine accepts its input.

Theorem 3.16 Every nondeterministic Turing machine has an equivalent deterministic Turing machine.

定理3.16：每个不确定性图灵机有一个等价的确定性图灵机。

注2：

DEFINITION 7.9

－Let N be a nondeterministic Turing machine that is a decider. The running time of N is the function f : N -> N, where f(n) is the maximum number of steps that N uses on any branche of its computation on any input of length n, as shown in the following figure.

定义7.9

－设N是一个不确定性图灵机，并且是个判定机。N的运行时间是函数f：N -> N， 对长度为n的输入，f(n)是N所有计算分支中的最大步数，如下图所示。

参考文献：

［1］Cook1971年的论文：  

cook1971.pdf

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