完成问题也是NP
我试图以一种直观的方式包围我听到的P，NP，NP-Complete和NP-Hard，这样我就不必记住他们的定义。
在下面的图片中（左边的场景，P！= NP），在NP-Complete和NP-Hard之间有一个重叠区域。 这是否意味着某些问题既是NP-Complete又是NP-Hard？ 根据这个特殊的答案，我发现这个矛盾：NP，NP-Complete和NP-Hard之间有什么区别？
上述链接中的表格说明NP-Complete问题可以在多项式时间内验证，而NP-Hard问题则不是。 那么怎么会有重叠呢？
NP完全性的部分定义是NP难的。 因此，每个NP完全问题都是NP难题。 这也反映了你的两个图表。
直到我在几个小时前修好它之前，链接到的表格都是错误的。 NP-Complete问题是NP问题的一个子集，根据定义，所有NP问题都可以在多项式时间内验证。 NP-难问题是那些至少与其他NP问题一样困难的问题（这是不直观的，因为不在NP中的问题可能是NP-难）。
要成为NP完成问题必须是
要在特定的复杂等级中完成，问题必须是
我们必须定义“至少同样艰难”。 假设我们在NP中有一个问题A. 为了证明它是NP-hard（因此是NP-Complete），我们证明NP中的所有问题都可以在多项式时间内转化为A. 由于A至少需要多项式时间求解，且多项式在加法下是闭合的，所以转换现在可以忽略不计，运行时间与A的运行时间相同（根据它的多项式与否）。
一旦你有一个NP完全问题，你可以证明一个问题在NP中NP是NP-hard（因此NP-Complete），通过另一个NP-Complete问题B并在多项式时间内将其转换为A.
我希望这可以清楚地表明NP-Complete是NP-hard的一个子集（并且链接到的表是错误的）。
链接地址: http://www.djcxy.com/p/6797.html