How can some NP-Complete problems be also 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.

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?.

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?

回答1:

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.

回答2:

The table you linked to was wrong until I fixed it a few hours ago. NP-Complete problems are a subset of NP problems, and all NP problems are verifiable in polynomial time by definition. NP-hard problems are those problems which are at least as hard as any other NP problem (which is sort of unintuitive, because problems not in NP can be NP-hard).

To be NP-Complete a problem must be

1. in NP
2. NP-hard

to be complete in a specific complexity class, a problem must be

1. in that complexity class
2. at least as hard as any other problem in that complexity class

We have to define "at least as hard". Suppose we have a problem A in NP. To prove it is NP-hard (and therefore NP-Complete), we show that all problems in NP can be converted to A in polynomial time. Because A takes at least polynomial time to solve, and polynomials are closed under addition, the conversion is now negligible, and the runtime is the same as the runtime of A (in terms of it being polynomial or not).

Once you have one NP-Complete problem, you can prove a problem A in NP is NP-hard (and therefore NP-Complete) by taking another NP-Complete problem B and converting it to A in polynomial time.

I hope this makes it clear that NP-Complete is a subset of NP-hard (and that the table you linked to was wrong).