“与法国朋友漫谈P vs NP”系列暂时告一段落，感谢所有参加对话的朋友！希望继续深化这样的讨论。

柳渝：Passe-Science，我逐条回复您：

1，“ P vs NP问题问“NP=P？”，实际上是问“NP-complete=P？”，所以P vs NP问题指向NP-complete。

Passe-Science： 从数学上讲，这二个问题是一回事：P与NP不同，当且仅当P与NP-complete不同。

从内容上看，“NP=P？”指在NP中找NP-complete，而NP-complete在NP中相当于“黑箱”，实际上是找不到这个“黑箱”的。而“NP-complete=P？”，比如说，可以指追本溯源研究NP-complete与P的关系，这是一条完全不同于现有NP-complete理论的研究方向，。。。

所以，从数学上讲，这二个问题是一回事；但实际上不是一回事。

2，Passe-Science：一个问题要能成为NP-complete问题，NP中的任何问题必须能够在多项式时间内归约为此问题。这是一个很强的特定属性，形式化准确地定义了所讨论的集合。

从定义上看，这个基于“归约”的定义“形式化准确地”定义了NP-complete。但是任给一个问题，是无法确定性判断该问题是否属于NP-complete的，因为不存在通用的算法将SAT问题归约该问题。比如，您在视频中讲的将SAT问题归约为3-染色问题的方法，只是一个“启发式”算法。

所以，基于“归约”的NP-complete定义是否“形式化准确地定义了所讨论的集合”，是需要判断的，。。。

这就是为什么讨论开始时我问：

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

2，NP的定义是否与人们认知P=NP？的困难有关?

Didier：我也认为，关于P=NP？讨论的困难来自西方世界的智力工具。

第一个困难来自字的构造，没有象形的基础，在不了解关键字构造的情况下（希腊语和拉丁语的学习），我在沟通时，希望但在大多数时候是信仰，对话者和我使用用的单词都指称同一对象。

比如，这里的“机器”已经有不同的定义，。。。，终极是“神喻机”！我要问问我的小孙女，她正在摆弄“独角兽”这个词，看起来与此很接近。

第二个困难来自建模，这是西方世界工业成功的强大工具：在实验科学中，对现实现象的研究导致提出了若干个理论模型；这些模型的操作促进了研究；最后，必须将理论结果与实际情况进行比较，从而有可能验证/排除某些模型等等；由此丰富了我们的知识。

这个来回的过程（对了！西方核心的“阴阳”？）非常有生产力。不幸的是，为了方便，为了充分性，甚至为了模式，我们忽略了与现实的对照来进行模型验证的关键阶段，有时我们甚至混淆了模型与现实。我们这个时代喜欢为所有事物建模（取决于人类的行为！不是吗，GAFA？），偏爱概念化，认定数学为纯科学，陶醉于概念化艺术（我们对此不懂，以至于取代宗教）。

在这里，起点是计算机及其可以在合理的时间内以编程方式解决的问题，模型之一是图灵机，理论操作此模型导致不确定性图灵机甚至“神喻机”的版本。从那里，还是要回到物理世界：面对当今的计算机世界的模型（思考所谓的由不存在的机器解决了的问题……意义何在？）

第三个困难来自于我们的语法或逻辑（有区别吗？）：我们解释事物的演讲看起来像演示，没给对话者的智慧留出余地：结构完善，是一系列旨在完全的论证和演绎，对话者陷入了争论；而在中文中，对话者却成为演员：讲话不完整，使接收方自己重做一些推理/演绎（这就是当我们教学时应该做的事情）。话语的危险存在于无形中引入错误的论证或概念的偷换（特别当我们处理的是一个概念的时候）：演讲的逻辑外观和连续的论证，没有留下时间对每个句子进行批判性分析，演讲漂亮，但结论……可能是不确定的。

在这里，不确定性程序的并行计算，几个不确定性动作与1个确定性动作的等价时间量度，未提供定义的“神喻机”的引入，这样的扭曲都被引入了论述中 。

第四个困难涉及到语言，或者说是语言的局限。语言在日常生活中用于解决我所感知的世界中的常见问题，是非常实用的，甚至是必不可少的。但是，如果我开始想探索这个世界的局限性，我会被引导说一种元语言：上帝，本质，宇宙，无限……当我们最终将这种元语言与语言混合时，我们就无法将这个世界与超越世界区分开了。

在这里，一开始我们讨论的是计算机和程序（还有更多的东西！），然后，我们使用数学语言来描述计算机和程序的功能，但是当我们开始陷入困境时，我们在数学语言之外引入了“神喻机（oracle）”（我们到达了天堂！）

柳渝：NDTM（不确定性图灵机）用来形式化定义NP，是由库克在其1971年著名论文中提出的。

我摘其中几段相关的文字[1]：

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

- 定理1 如果在多项式时间内某些不确定性图灵机接受了一个字符串集S，那么S可以P-归约为{DNF重言式}。

（这里，S对应NP， {DNF tautologies}对应SAT问题）

In order to make this notion precise, we introduce query machines, which are like Turing machines with oracles in [1]. 

为了使这个概念更加精确，我们引入“查询机”，它们就像[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 assumes 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. 

查询机是多带图灵机，具有称为查询带的特别带，以及分别称为查询，yes和no三种不同的状态。如果M是查询机，T是一组字符串，那么M的T计算是M的一个计算，其中最初M处于初始状态，在其输入带上输入字符串w，每次M 假设在查询状态，查询磁带上就有一个字符串u，如果u∈T，则M承担下一个状态为yes状态；如果u∈/ T，则为no状态。 我们想到一个“神喻机（oracle）”，它知道T，将M置于yes状态或no状态。

参考文献：

[1] Stephan Cook, The Complexity of Theorem-Proving Procedures, 1971:

https://www.inf.unibz.it/~calvanese/teaching/11-12-tc/material/cook-1971-NP-completeness-of-SAT.pdf