柳渝：我用“ imaginaire （想象）”一词指如您所说“有些微妙”的NDTM，确实容易产生歧义。实际上，大致存在三种对NDTM的解释：

- NDTM具有无限的并行能力；

- NDTM可用TM在指数时间模拟；

- Oracle（Cook原始关于NDTM的定义）。

我们暂时把基于“有些微妙”的NDTM的“定义1”放在旁边，再考察一下基于TM的“定义2”。

在人们的常识认知中，NP与P是不同的。但是当人们希望对NP做深入的了解时，“定义2”告诉人们：NP是图灵机多项式时间可验证解的问题类，由于P也是其解可以容易验证的问题类，所以NP包括P。注意，NP与P的关系从“相对关系”变成了“包含关系”。

所以，我问：这样的NP定义是否存在着问题？我现在试用一个比喻来说明我的质疑：

柳渝认识“牛”，但是没见过“马”，一天她见到一群牛和一群“马”在一起吃草，于是问您：

柳渝（指着马）问：这是什么？

Passe-Science：这是“马”。

柳渝：什么是“马”？

Passe-Science：“马”是有颜色的动物。

现在Passe-Science问柳渝：您知道什么是“马”了吗？

柳渝只能回答：我不知道，因为牛也是有颜色的动物。

Passe-Science：我明白了混淆所在。根据定义，P包含在NP中是完全容许的。从结构上讲，无论哪种定义（定义1或定义2），P总是包含在NP中的。

如果问题是P，那么很明显，它可以在不确定性图灵机（定义1，因此也是NP）上多项式时间内求解，也可以在多项式时间内验证（定义2，因此也是NP）。

从来没有一个（P与NP）“对立”关系的定义，没有任何尝试能将NP定义为与P“不相交”的集，它们一直是包含关系，我们正在尝试的是研究这种包含关系是严格的，还是实际上相等的，NP中是否存在不在P中的元素。

关于“不相交”，应该是对“NP完全类”而言的，但显然我们不确定（因为是整个问题）NP中的“NP完全问题”在某种程度上是“最难”或“至少一样难”。如果我们有不同NP的P，那么P和NP-Complete之间是分离的。

参考文献：

对话原文见【1】https://www.youtube.com/watch?v=8TrIW-4kfRg