0

Wiki 说，当您将 poly time 中的 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

我应该相信哪一个？

4

1 回答 1

2

两个都。NP-complete 是 NP-hard 的一个子集；根据定义，NP 完全问题是 NP 难题。如果您只想记住一个陈述，请记住后者：如果 NP-hard 中的问题可以在多项式时间内简化为问题 A，那么 A 也是 NP-hard。

就其价值而言，NP-hardness 是指 NP 中的任何问题都可以简化为多项式时间内的问题的情况。NP-completeness 是指问题既属于 NP 又属于 NP-hard 的情况。

于 2012-02-25T15:51:35.480 回答