如何通俗的向别人描述 P=NP 问题?

发布于 08-30 16:40 字数 160 浏览 21 评论 0

看到 P = NP 问题最短的描述:如果是/不是问题的正面答案可以很快验证,其答案是否也可以很快计算?
还是不够通俗啊。有更好的描述吗?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

养猫人2022-09-06 16:40:03

是否所有可以简单地验证答案(是否正确)的问题,也同样可以简单地计算出答案。

推荐「可能与不可能的边界:P/NP问题趣史」,这是一本阅读起来比较轻松的科普书,介绍了一些有关 P/NP 的简单知识。

对你的占有欲2022-09-06 16:40:03

人類視角是否可以等於上帝視角。

或者:

機器視角是否可以等於人類視角。


解釋見我在@王子亭的回答下的評論


更詳細一點的解釋:真的是否一定是可證的。

再可℃爱ぅ一点好了2022-09-06 16:40:03

一个亚马逊网友 在《可能与不可能的边界:P/NP问题趣史》 书评吧算是
简单地说,P 是否等于 NP 可以表述如下:验证 一个(NP)判定问题的难度是否和 求解 该问题的难度一样?以旅行商问题(是否可从一个地图上某城市出发,经过所有的城市一次且仅一次)为例:验证是指给出一条路线看它是否符合上述条件,求解是指回答该图是否有一个符合要求的路线?直觉上前者要简单一些,因为直接按地图一步步查验即可,但后者是感觉是计算上很难的。 前者是一个 P 问题,而后者是一个 NP 完全问题。如果 P = NP,则这两个问题一样难。但人们感觉上,这两者的难度应当是不一样的。这正是 P v.s. NP 问题的困惑所在。

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文