某些NP完全问题又如何成为NP-Hard? [英] How can some NP-Complete problems be also NP-Hard?

问题描述

我正在尝试以一种直观的方式将听到的内容围绕在P，NP，NP-Complete和NP-Hard上，这样我就不必记住它们的定义了.

I'm trying wrap my heard around P, NP, NP-Complete and NP-Hard in an intuitive way so that I don't have to remember their definitions.

在下面的图像中(左手场景，P！= NP)，NP-Complete和NP-Hard之间存在重叠区域.这是否意味着NP-Complete和NP-Hard都存在一些问题?根据此特定答案，我发现这是矛盾的:

In the following image (the left hand scenario, P != NP), there's an overlapping area between NP-Complete and NP-Hard. Does it mean that some problems are both NP-Complete and NP-Hard? I find that contradictory, according to this particular answer: What are the differences between NP, NP-Complete and NP-Hard?.

上面链接中的表格显示，可以在多项式时间内验证NP-Complete问题，而不能验证NP-Hard问题.那么怎么会有重叠呢?

The table in the above link says an NP-Complete problem is verifiable in polynomial time and an NP-Hard problem is not. So how can there be an overlap?

推荐答案

NP完整性的部分定义是NP困难的.因此，每个NP完全问题都是NP难的.您的两个图表也都反映了这一点.

Part of the definition of NP-completeness is being NP hard. Therefore, every NP-complete problem is NP-hard. This is also reflected by both of your graphs.

这篇关于某些NP完全问题又如何成为NP-Hard?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！