最近我与一个工作在NP问题实际求解前沿的同事对话：

同事：我认为，如果取消了“不确定性图灵机（NonDeterministic Turing Machine NDTM）”这个概念，把NP定义成“确定性图灵机（Deterministic Turing Machine DTM）”在多项式时间内可验证的问题类，不会影响NP问题的实际求解，对NP完备理论也不会产生影响。

柳渝：此议题涉及到二个层次，NP问题的实际求解和NP问题的理论研究。若取消NDTM，就NP理论而言，人们自然会问诸如此类问题：

－为什么所有关于NP完备理论的文献和书籍，都要花重要的篇幅讲NDTM？

－若NDTM无用，为什么仍然要将此无用的概念灌输给学子们，混淆他们的认知，让他们越学越晕？

－NP完备理论的核心是Cook定理（注），而Cook定理的陈述和证明都是建立在NDTM基础之上的，如果取消了NDTM，如何阐述Cook定理？如何理解NP完备理论？

注：The original statement of Cook’s theorem was presented in Cook’s paper entitled “The complexity of theorem proving procedures” as:

－Theorem 1 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 main idea of the proof of Theorem 1 was described:

－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.