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

博文

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

已有 1445 次阅读 2020-5-16 16:18 |个人分类:不确定性问题和算法讨论|系统分类:海外观察

同事Didier是我多年的同事好友,Louis是大学经济系退休教师,对我的P vs NP问题研究感兴趣,有了如下对话。


首先DidierLouis推荐了一个很受欢迎的法语普及P vs NP的视频【1】。然后,给Louis作了一些介绍,我接着说:


这个视频很好!可惜他用逻辑和数学的方法清楚地解说一个错误的问题:P vs NP,。。。这不是他的错,而是学界的流行观念。


P vs NP问题由Cook1971年形式化提出后,现在通俗表达为:当一个问题的解可以容易验证(NP),其解也可以容易找到吗(P)?2 此后学界围绕着这个世纪难题研究至今,仍然没有实质性的结果。


我试用一个比喻来说明我的观点:


比如,柳渝认识,但是没见过,一天她来到法国,见到一群牛和一群在一起吃草,于是问路易:

柳渝(指着马)问:这是什么?

路易:这是

柳渝:什么是

路易:是有颜色的动物。


如果路易接着问柳渝:你现在知道什么是了吗?


柳渝能回答什么?你们怎么看路易的回答?


参考文献:

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://wap.sciencenet.cn/blog-2322490-1233457.html

上一篇:简介“逻辑谬误”- 谬误分类
下一篇:与法国朋友漫谈P vs NP(2)

1 杨正瓴

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

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

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

GMT+8, 2021-12-4 07:31

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部