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

博文

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

已有 1866 次阅读 2020-5-20 12:17 |个人分类:不确定性问题和算法讨论|系统分类:科普集锦

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


柳渝:我提一个问题:


您举了3NP问题的例子:3-图染色问题,背包问题,合取范式可满足问题(SAT问题)。


于常识认知中,我们知道NPP是不同的,因为与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



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

上一篇:与法国朋友漫谈P vs NP(2)
下一篇:与法国朋友漫谈P vs NP(4)

5 谢力 杨正瓴 张鹰 王宏琳 刘钢

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

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

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

GMT+8, 2024-3-29 14:43

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部