Complete problems be also NP

 

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?

在这里输入图像描述

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.

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

  • in NP
  • NP-hard

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

  • in that complexity class
  • 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).

    链接地址: http://www.djcxy.com/p/6798.html

    上一篇: 不是NP的难题

    下一篇: 完成问题也是NP