Why is the class NP-Complete important compared to NP-hard?

Problem Detail: 

I'm studying computational complexity and I was wondering why the NP-Complete (NPC) problems is an important class at all. I find it obvious why we're interested in showing a given NP problem is NP-hard.

I also understand the definition of NPC, and that showing a given decision problem is NP-hard, knowing it is in NP, is exactly was NPC means.

However, what I don't understand is: why this concept is so important? Surely, if we find any NP-hard algorithm which runs in time P (whether or not that is in NP), we have shown that $NP = P$.

Why is this concept so important?

Asked By : Amnestic

Answered By : Luke Mathieson

There are at least a few reasons that NPC is interesting:

• The class NP contains many problems that are interesting (both practically and theoretically), moreover many of these problems turn out to be NP-hard (and hence NP-complete), but many problems outside of NP are almost certainly too hard to be of more than theoretical interest, so NPC provides a (rough) group of problems that are apparently hard, but not so hard that we can't try to do something with them.
  In other words, NPC is probably the limit of what we can hope might be polynomial-time solvable, it would seem a stretch to try for PSPACE = P (for example).
• The class is NP is structurally interesting. It's the basic example of "do we get any more computational 'speed' from nondeterminism". So we're interested whether P=NP or not, and NPC is (probably) an important component of working that out.
• NP-hard (as a class) is really too big and varied to deal with as a single thing, it's everything that can be reduced to from an NP-complete problem, including a huge swathe of stuff outside NP, so from the point of view of trying to develop general results and techniques, there's nothing to grab on to.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43159