问如果P= NP，为什么P= NP =NP-完全？
EN

Stack Overflow用户

提问于 2014-12-11 14:02:06

回答 1查看 1.5K关注 0票数 0

如果是P = NP，为什么P = NP也等于NP-Complete

也就是说，为什么P = NP = NP-Complete会出现这种情况

假设P != NP，在NP中存在问题，而不是在NP - Complete中。当P = NP时，所有NP问题现在实际上都是P。

NP - Complete中不应该还有P = NP问题吗？

complexity-theory

computation-theory

回答 1

Stack Overflow用户

发布于 2014-12-11 14:33:36

为便于将来参考，无代码=不属于堆栈溢出...

对于你的回答，http://en.wikipedia.org/wiki/NP-complete提供了完整的解释。在“门外汉”术语中，所有NP问题都可以用多项式转换器转换成NP-C问题。这意味着如果P=NP，所有NP都可以转换为NP-C，根据定义，NP-C可以转换为另一个NP-C，等等，所以P=NP=NP-C。

票数 2

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

原文链接：

https://stackoverflow.com/questions/27416362

复制

相似问题

问如果P= NP，为什么P= NP =NP-完全？
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如果P= NP，为什么P= NP =NP-完全？EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如果P= NP，为什么P= NP =NP-完全？
EN