问归约为np困难
EN

Stack Overflow用户

提问于 2012-02-25 17:46:38

回答 1查看 219关注 0票数 0

维基说，当你在多时间内将np复杂问题转化为A时，A是np困难的。请参阅http://en.wikipedia.org/wiki/NP-hard

但是下面的pdf说，当你在多项式时间内将np困难问题转化为问题A时，A是np - hard http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard.pdf

我应该相信哪一个？

回答已采纳

发布于 2012-02-25 23:51:35

两者都有。NP-complete是NP-hard的一个子集；根据定义，NP-complete问题是NP-hard。如果你只记住一句话，记住后者:如果NP-hard中的一个问题可以在多项式时间内归结为问题A，那么A也是NP-hard。

就其价值而言，NP -硬度是指NP中的任何问题都可以归结为多项式时间内的问题。NP -完备性是指问题既在NP中又在NP-hard中的情况。

票数 2

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

原文链接：

https://stackoverflow.com/questions/9442938

复制

相似问题

问归约为np困难EN