19
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ I've removed your second question because it's completely separate from the first. However, it is a very good question and I encourage you to ask it as a new question. To recover the text, click the "edited [at whatever time]" link, which will show you the edit history and let you copy-paste the text. $\endgroup$
    – David Richerby
    Jun 2, 2015 at 8:30

3 Answers 3

Reset to default
16
$\begingroup$

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.
Improve this answer
$\endgroup$
3
  • $\begingroup$ Since my original question was edited to reflect the title, maybe you should hide the answer of the second question as well. $\endgroup$
    – Amnestic
    Jun 2, 2015 at 15:56
  • 1
    $\begingroup$ NP-hard is not "everything outside of NP", as it includes (at least) the NP-complete problems in NP. I understand what you mean, but don't know how to state it succintly. $\endgroup$
    – vonbrand
    Aug 24, 2015 at 18:35
  • $\begingroup$ @vonbrand, yes, I wildly overstated that (bout of insanity maybe?). The new version is accurate, but it doesn't quite have the feeling unfortunately. $\endgroup$
    – Luke Mathieson
    Aug 25, 2015 at 1:22
9
$\begingroup$

From the point of view of someone who writes code for a living, having a good familiarity with NP-completeness is important for:

1. Recognizing when you're barking up the wrong tree

NP-complete problems are the easiest of the NP-hard problems and yet as far as we can tell, it takes time exponential to the size of the input to solve such a decision problem. So, as a practical matter if you can show that the problem you're trying to solve is NP-hard (typically by showing that an efficient solution to it would also give an efficient solution to some NP-complete problem), you know that you can stop searching for an efficient algorithm to solve it exactly in general. Instead, you can select from known algorithms that promise good approximations for NP-hard optimization problems and get on with the rest of your project.

2. Finding the right tree

Because computers are often used to attack NP-hard problems, specialized solvers have been developed that can efficiently solve some NP-hard problem instances. Recognizing that your problem is NP-complete is the first step toward finding an existing tool (SAT, ILP, SMT, CSP to name a few) that might help you find exact solutions in some cases where you otherwise would have had to settle for an approximation.

Improve this answer
$\endgroup$
-3
$\begingroup$

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

Every NP problem reduces to any NPC problem, but it's not true that every NP problem reduces to any NP-hard problem, so proving an algorithm NP-hard is in P doesn't prove P=NP at all. It would be the case, however, for a NPC problem, that is precisely what "reduces" means. So, if we find an P algorithm for a NPC problem, then, we will have proven that P=NP.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Sorry but this is incorrect. The definition of a problem $X$ being NP-hard is that every problem in NP reduces to $X$. $\endgroup$
    – David Richerby
    Jun 12, 2015 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.