与法国朋友漫谈P vs NP缘起于Youtube上一个很受欢迎的法语普及P vs NP的视频【1】，所以我直接和此视频制作者Passe-Science对话。我将对话译成中文分享：

柳渝：我提一个问题：

您举了3个NP问题的例子：3-图染色问题，背包问题，合取范式可满足问题（SAT问题）。

于常识认知中，我们知道NP与P是不同的，因为与P相反，NP现在只有指数时间的精确求解的穷举法，和多项式时间的近似算法。然而，NP被定义成“其解可以容易验证的问题”，但是，P也是其解可以容易验证的问题。

那么，这个“其解可以容易验证”的性质如何能捕捉到在直觉上与P不同的NP的本质？

Passe-Science : 我不肯定完全理解了您的问题，但我认为我基本明白了。

大致说，您是想知道我们如何能够“严格”定义NP类和P类。 （不依靠直觉，直觉形式上不严谨）

因此，当我们进入严格的框架时，我们这里仅研究所谓的“判定”问题，即以答案为“是或否”的形式表述。

例如，“我可以用3种颜色为这张图着色吗？” （而不是询问如何用算法进行操作）。

在所有判定问题中，我们定义2个类：

P类：诸如通用图灵机（这是计算机的严格形式化）上的可编码算法之类的问题，以多项式复杂度回答该问题。

NP类：对于不确定性多项式，询问是否存在多项式时间的不确定性图灵机算法。

第二个严格定义有些微妙，粗略地讲，这等于是赋予了机器无限的并行能力，使它可以并行测试所有解决方案的能力。因此，我们有了2个严格的，不同的定义来定义这两个类。但可能这二个定义尽管不同，却定义了一个对象（如果P = NP）。

然后是一个NP完全类，这是一个令人惊讶的事实：我们可以证明NP类中存在特定问题，可以在多项式时间内归约任何其他NP问题。 NP-完全类不是空的，在开始时这一点是不明显的，是Cook-Levin定理给出了NP-完全问题的第一个例子。

然后，一旦有了这个例子，此后就很容易证明其他问题是NP完全的，只要证明我们可以将它们归约为该特定例子，我们已经归约了一些例子。（这就是我在视频中所做的）。

如果我没有回答您的问题，请随时澄清。

参考文献：

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