如何通俗的向别人描述 P=NP 问题?
看到 P = NP 问题最短的描述:如果是/不是问题的正面答案可以很快验证,其答案是否也可以很快计算?
还是不够通俗啊。有更好的描述吗?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(3)
再可℃爱ぅ一点好了2022-09-06 16:40:03
一个亚马逊网友 在《可能与不可能的边界:P/NP问题趣史》 书评吧算是
简单地说,P 是否等于 NP 可以表述如下:验证 一个(NP)判定问题的难度是否和 求解 该问题的难度一样?以旅行商问题(是否可从一个地图上某城市出发,经过所有的城市一次且仅一次)为例:验证是指给出一条路线看它是否符合上述条件,求解是指回答该图是否有一个符合要求的路线?直觉上前者要简单一些,因为直接按地图一步步查验即可,但后者是感觉是计算上很难的。 前者是一个 P 问题,而后者是一个 NP 完全问题。如果 P = NP,则这两个问题一样难。但人们感觉上,这两者的难度应当是不一样的。这正是 P v.s. NP 问题的困惑所在。
~没有更多了~
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
是否所有可以简单地验证答案(是否正确)的问题,也同样可以简单地计算出答案。
推荐「可能与不可能的边界:P/NP问题趣史」,这是一本阅读起来比较轻松的科普书,介绍了一些有关 P/NP 的简单知识。