在计算复杂性理论中，NP的形式化定义是：“NP是NDTM（NonDeterministic Turing Machine）多项式时间可接受的语言”，即“NP是NDTM多项式时间可判定解的存在的问题”。

这里我们追本溯源NP概念形成的历史，揭示NDTM指称两个本质完全不同的概念，初析NDTM的歧义性。

一，Cook定理中的NDTM

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

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

这里的{DNF tautologies}等价于合取范式，“a set S of strings is accepted by some nondeterministic Turing machine ”就是现在NP问题的形式化定义，即NP是NDTM在多项式时间内可接受的语言类。

关于NDTM的计算，Cook的文章说：

－假设NDTM（M）在多项式时间Q（n）内接受一组字符串S。给M输入一个表达实例的w，我们将构造一个合取范式（CNF）A（w），使得当M接受w时A（w）是可满足的。

－粗略地说，如果合取范式即刻（通过“神谕机”）被判定，那么这些问题就可以在多项式时间内被判定。为了使这个概念准确，引入“查询机”，“查询机”就像在图灵机中装配一个“神谕机”。

－查询机是一台多带图灵机，其中一条带被称为“查询带”，有三种状态：query状态，yes状态和no状态。M是查询机，T是一组字符串，则M的“T计算”就是M的计算：M最初处于初始状态，并且在其输入带上有字符串w，并且每次M确保查询状态在查询带上有一个字符串u，如果u∈T，则下一个状态M保证进入yes状态，如果u ̸∈T，则进入no状态。这里有“神谕机”认识T，把M置于“yes”或“no”状态。

－Suppose a nondeterministic Turing machine M accepts a set S of strings within time Q(n), where Q(n) is a polynomial. Given an input w for M, we will construct a propositional formula A(w) in conjunctive normal form (CNF) such that A(w) is satisfiable iff M accepts w. Thus ¬A(w) is easily put in disjunctive normal form (using De Morgans laws), and ¬A(w) is a tautology if and only if w ̸∈ S. Since the whole construction can be carried out in time bounded by a polynomial in | w | (the length of w), the theorem will be proved.

－By reduced we mean, roughly speaking, that if tautology hood could be decided instantly (by an ”oracle”) then these problems could be decided in polynomial time. In order to make this notion precise, we introduce query machines, which are like Turing machines with oracles in [1].

－A query machine is a multitape Turing machine with a distinguished tape called the query tape, and three distinguished states called the query state, yes state, and no state, respectively. If M is a query machine and T is a set of strings, then a T-computation of M is a computation of M in which initially M is in the initial state and has an input string w on its input tape, and each time M assures the query state there is a string u on the query tape, and the next state M assumes is the yes state if u ∈ T and the no state if u ̸∈ T . We think of an ’oracle’, which knows T, placing M in the yes state or no state.

由此可见，这里的NDTM实质上是“神谕机”，也就是说，“NP是NDTM在多项式时间内可接受的语言”，实际上指“NP是神谕机在多项式时间内可接受的语言”。

然而“神谕机”只是图灵用来指称“不可判定问题”的一种无奈的表达，在现实中并不存在，所以后来“神谕机”就被偷换成了基于“非确定型自动机”的NDTM！

二，流行NP定义中的NDTM

流行NP定义中的NDTM，指在计算的每一时刻，根据当前状态和读写头所读的符号，机器的下一个动作存在“多选择”。

对于NP问题，NDTM的计算实际上是“猜测＋验证”：对于表达成字符串w的一个实例，图灵机只能在多项式时间“猜测”出一个候选解c（证书），并能在多项式时间“验证”c，若验证回答yes，则c是w的解，图灵机“接受”w。然而这里的关键是，若验证回答no，只能说明c不是w的解，却不能由此判断w没有解，也就是说，w可能有解也可能无解，故no的判断是“不确定的”，因此图灵机还不能“拒绝”w，需要回溯，继续搜索，如此可能遍历整个搜索空间，是有指数时间复杂度的“穷举法”。

可见此NDTM的计算实际上是TM的计算，故NDTM本质上是TM，如Sipser书中Theorem 3.16所说，“Every nondeterministic Turing machine has an equivalent deterministic Turing machine”。

作为一种思想实验，不妨说“NP是NDTM（神喻机）在多项式时间内可以判定解的存在的问题”，但这只是借此表达“NP是TM在多项式时间内不可以判定解的存在的问题”，而不是“NP是NDTM（TM）在多项式时间内可以判定解的存在的问题”！换句话说，NP定义中的NDTM出现了歧义性。

参考文献：

[1] Stephen Cook, The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151-158 (1971). (http://theory.stanford.edu/~trevisan/cs172-07/cook.pdf)

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

＊＊＊＊＊＊

Analysis of two sources for NDTM - Ambiguity of NDTM

In computational complexity theory, NP is formally defined as the class of languages accepted by NDTM (NonDeterministic Turing Machine) in polynomial time, that is, the class of problems for which the existence of solutions are decidable by NDTM in polynomial time.

Here, we trace the history of taking shape of the NP concept, and show that NDTM in fact refers to two completely different concepts.

1. NDTM in Cook's theorem

NDTM was used to define NP in Cook's article "The Complexity of Theorem Proving Procedures" (1971) that laid the foundation of computational complexity theory.

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

The expression of "a set S of strings is accepted by some nondeterministic Turing machine within polynomial time" becomes later the definition of NP as the class of languages accepted by NDTM in polynomial time.

Concerning NDTM, Cook's article states:

－Suppose a nondeterministic Turing machine M accepts a set S of strings within time Q(n), where Q(n) is a polynomial. Given an input w for M, we will construct a propositional formula A(w) in conjunctive normal form (CNF) such that A(w) is satisfiable iff M accepts w. Thus ¬A(w) is easily put in disjunctive normal form (using De Morgans laws), and ¬A(w) is a tautology if and only if w ̸∈ S. Since the whole construction can be carried out in time bounded by a polynomial in | w | (the length of w), the theorem will be proved.

－By reduced we mean, roughly speaking, that if tautology hood could be decided instantly (by an ”oracle”) then these problems could be decided in polynomial time. In order to make this notion precise, we introduce query machines, which are like Turing machines with oracles in [1].

－A query machine is a multitape Turing machine with a distinguished tape called the query tape, and three distinguished states called the query state, yes state, and no state, respectively. If M is a query machine and T is a set of strings, then a T-computation of M is a computation of M in which initially M is in the initial state and has an input string w on its input tape, and each time M assures the query state there is a string u on the query tape, and the next state M assumes is the yes state if u ∈ T and the no state if u ̸∈ T . We think of an ’oracle’, which knows T, placing M in the yes state or no state.

It shows that NDTM is by nature "Oracle". However, Oracle is only a concept in thought experiments borrowed by Turing in his doctoral dissertation to represent something opposed to Turing Machine (TM), so it cannot carry out a real computation.

2. NDTM in current definition of NP

Later, that NDTM based on Oracle is replaced by NDTM based on Automaton which is used to define the current NP. However, this NDTM is by nature of TM, as described in Theorem 3.16 of the Sipser's book, "Every nondeterministic Turing machine has an equivalent deterministic Turing machine."

For a NP problem, the computation of this NDTM consists of "guessing + verifying". Given an instance expressed as a string w, the NDTM guesses a candidate solution c (certificate) in polynomial time and then verifies it in polynomial time. If the verification answer is "yes", then c is determined as solution to w, and this NDTM accepts w. However, the key point here is that if the verification answer is "no", which only shows that c is not a solution to w, but it cannot determine that w does not have any solution, that is, w may or may not have solution. Therefore, this NDTM cannot refuse w, and needs to backtrack and continues searching. This search may traverse the entire search space, where is from the brute-force search with exponential time complexity. In this way, the existence of solutions for a NP problem is not decidable by NDTM in polynomial time!

As a thought experiment, it might say that NDTM (Oracle) is used to determine the existence of solutions for a NP problem in polynomial time, but in reality NDTM (TM) cannot determine the existence of solutions for a NP problem in polynomial time!

In other words, NDTM refers to two completely different concepts, which is the source of the ambiguity of NP.

Reference:

[1] Stephen Cook, The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151-158 (1971). (http://theory.stanford.edu/~trevisan/cs172-07/cook.pdf)

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