开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >假设P= NP

问假设P= NP
EN

Stack Overflow用户

提问于 2021-12-16 00:11:15

回答 1查看 54关注 0票数 2

假设P= NP，这是否意味着哈密顿循环不再是NP-硬的？哈密顿圈是一种语言，其中一个给定的图G包含一个火腿圈.

EN

回答 1

Stack Overflow用户

发布于 2021-12-16 00:15:58

NP-Hard的定义是，它允许您解决NP -完全问题，这是一种奇特的说法：“解决这个问题至少和解决任何NP问题一样困难”。

如果P= NP，则NP硬问题保持NP难，即“解决这个问题至少与解决任何NP问题一样困难”。但由于P= NP，这相当于“解决这个问题至少和解决任何P问题一样困难”。一般认为这并不难

票数 1

EN

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/70371817

复制

相似问题