科学网

 找回密码
  注册
搜索
热搜: 科学 论文
搜索
与法国朋友漫谈P vs NP(3)
热度 1 柳渝 2020-5-20 12:17
与法国朋友漫谈P vs NP缘起于Youtube上一个很受欢迎的法语普及 P vs NP 的视频【 1 】,所以我直接和此视频制作者Passe-Science对话。我将对话译成中文分享: 柳渝: 我提一个问题: 您举了 3 个 NP 问题的例子: 3- 图染色问题,背包问题,合取范式可满足问题( SAT 问题) ...
个人分类: 不确定性问题和算法讨论|1442 次阅读|1 个评论 热度 1
与法国朋友漫谈P vs NP(2)
柳渝 2020-5-18 17:31
现在我回到 P vs NP 。 通俗说, P ( Polynomial )指计算机求解容易的问题,即存在多项式时间精确算法,比如 GPS 中寻找任意二个地点之间的最短距离。 NP ( Non-deterministic Polynomial )指计算机求解困难的问题,比如视频举的 3 个例子: 3- 图染色问题,背包问题,合取范 ...
个人分类: 不确定性问题和算法讨论|1513 次阅读|没有评论

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

GMT+8, 2022-6-28 01:53

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部