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

博文

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

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

现在我回到P vs NP


通俗说,PPolynomial)指计算机求解容易的问题,即存在多项式时间精确算法,比如GPS中寻找任意二个地点之间的最短距离。


NPNon-deterministic Polynomial)指计算机求解困难的问题,比如视频举的3个例子:3-图染色问题,背包问题,合取范式可满足问题(SAT问题),这些问题只有精确求解的指数时间穷举法,或多项式时间近似算法。

image.png

在人们的常识认知中,NPP是不同的,但是当人们希望对NP做深入的了解时,学界告诉人们:NP是其解可以容易验证的问题,比如:视频中3-图染色问题的例子,给图用3种颜色着色,可以容易验证此着色是否满足相邻两点是否着同一色。


接着说,当然P也是其解可以容易验证的问题,现在问题是:“NP是否等于P?” - 这就是世纪难题P vs NP”


你们怎么看这个问题?这样的NP定义方式与前面Louis回答我“什么是马?”是否似曾相识(与法国朋友漫谈P vs NP(1))?


参考文献:

1https://www.youtube.com/watch?v=8TrIW-4kfRg

2May 2, 2013 (The New Yorker)A Most Profound Math Problem Alexander Nazaryan。中文译文:http://blog.sciencenet.cn/blog-2322490-995211.html





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

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

2 杨正瓴 张鹰

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

数据加载中...

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

GMT+8, 2024-3-29 09:52

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部