柳渝：是的，我期待一个与常识认知一致的NP定义，但并不排除直觉：

“除了明显的直觉和必要的推理外，人们没有其他方法可以了解真相。” -笛卡尔

您解释NP的形式化定义：

- 定义1: NP是不确定性图灵机多项式时间可判定的问题。

问题是这里的“不确定性图灵机”在现实中不存在，如您所解释，“这等于是赋予了机器无限的并行能力，使它可以并行测试所有解决方案的能力”；在Cook定理（1971年论文）中则指“神喻机”。

实际上，NP的非形式定义（NP是其解可以容易验证的问题）也可以进一步形式化：

- 定义2: NP是图灵机多项式时间可验证（解）的问题。

然而，NP的这二个定义似乎所指不同：定义1将NP与P“分开”，但是基于现实中不存在的（想象的）“不确定性图灵机”；定义2虽然基于现实的“图灵机”，但又将NP与P混淆了。

于常识认知，不同定义之间的区别在于抽象的程度和表达的方式不同，应该具有一致性，即所指应该是同一事物。

所以，我的问题是：

1，NP的定义是否存在着问题？

2，NP的定义是否与人们认知P vs NP问题困难有关（如您视频的留言所说，几乎所有学习计算复杂性理论的人理解P vs NP都有困难）？

Passe-Science：您说“定义1将NP与P’分开’，但是基于’imaginaire （想象的）’的不确定性图灵机；定义2虽然基于’现实’的图灵机，但又将NP与P混淆了。”

对于“ imaginaire （想象）”一词有点值得怀疑，因为所有数学都是抽象模型，甚至数字1，确定性图灵机和不确定性图灵机也都是抽象模型。

至于说“算法的复杂性”，从定义上讲是一种无限的行为，因此也是一个抽象模型等等。但是，仅是为了说明，我不会在意义或缺乏意义，某些数学模型是真实或不是真实的，做太多论述。 

简单回应您的段落，有几件事存在混淆：

1）“判定问题”整体而言，例如“找到一个过程来回答任何图任意图是否为3色”，处于无穷实例集，在这个层次上我们可以说算法的复杂性。

2）在实例层次上，即给定一个图， “此图G是3色的吗？”

3）针对给定的实例和一个候选解，问：“此图的3-着色是有效的吗？” 如果要在这种情况下谈论复杂性，我们将对所有可能的图实例+候选着色进行推理。

而且，您采用NP的“定义2”，它与P类的定义完全不同，因为它们不在同一层次。

P是可以在多项式时间内“解决”的判定问题类（即我们仅向算法提供问题实例，在此为图G，算法必须在多项式时间内回答这个问题是3色的）。

NP是可以在多项式时间内“验证”的判定问题类。 （但尚未解决，也就是说，我们为算法提供了问题的实例，例如给定的图和着色方案，算法的工作只是判定3-着色的有效性，而不是对“3-着色能力”的判断）。

因此，对于P类和NP类，在两种情况下确实存在多项式复杂度的概念，但并不是针对同一件事物。

您说“定义1将NP与P分开”。定义1和2在数学上是等价的，因此，如果定义似乎“分隔”某些东西（或您对定义1的结论），则定义2会做相同的事情。

定义1是表达在不确定性图灵机上多项式时间的“可求解性”，定义2是表达在确定性图灵机上以多项式时间的“可验证性”。而且，正如我在上文中所述，在二种情况的“多项式”不是做相同的事情。

更清楚吗？

参考文献：

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