不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

与法国朋友漫谈P vs NP(8)

已有 2378 次阅读 2020-6-4 15:10 |个人分类:在中法文化之间流连|系统分类:科普集锦

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


柳渝:Passe-Science,我逐条回复您:

1“ P vs NP问题问“NP=P,实际上是问“NP-complete=P,所以P vs NP问题指向NP-complete

Passe-Science 从数学上讲,这二个问题是一回事:PNP不同,当且仅当PNP-complete不同。


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


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


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


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


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


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

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

2NP的定义是否与人们认知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}.

定理如果在多项式时间内某些不确定性图灵机接受了一个字符串集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. 

查询机是多带图灵机,具有称为查询带的特别带,以及分别称为查询,yesno三种不同的状态。如果M是查询机,T是一组字符串,那么MT计算是M的一个计算,其中最初M处于初始状态,在其输入带上输入字符串w,每次M 假设在查询状态,查询磁带上就有一个字符串u,如果uT,则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






https://m.sciencenet.cn/blog-2322490-1236420.html

上一篇:数字“三” - 中西文化阐释(2)
下一篇:数字“三” - 中西文化阐释(3)

1 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 16:36

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部