||
“与法国朋友漫谈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
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-1 08:23
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社