I keep hearing questions about whether something is NP-complete, but they never really mention what it is. Why do people care so much about NP-complete problems?


4 Answers 4


A problem is in class NP if its solution may be verified in polynomial time, that is if the dimension of the problem is n you may be sure that for large enough n you need less than r·nk operations to verify the solution.

A problem is in class P if its solution may be found in polynomial time, instead. A problem in P is in NP by definition, but the converse may not be the case; probably the most important open question in computer science is whether classes P and NP are the same, that is P=NP.

NP-complete is a family of NP problems for which you know that if one of them had a polynomial solution then everyone of them has.

(EDITED) For the time being, only known algorithms for NP-complete problems are exponential in number of operations, so they are not practically solvable for n large.

  • 6
    $\begingroup$ You mean "only known algorithms for NP complete problems" $\endgroup$ Jul 26, 2010 at 15:29

To expand on Mau's answer, you should care about NP-complete problems because there is an entire family of them that spans a large number of seemingly basic algorithms across a wide range of disciplines. These aren't obscure problems, but extremely important and highly practical questions. For examples, consider the following:

  • Travelling salesman problem - finding the shortest path (on a graph) that allows you to visit every city exactly once.
  • Bin packing problem - there are a number of fixed (integer) size bins and objects of varying sizes. Minimise the number of bins required to hold all of the objects
  • Knapsack problem - given objects of various sizes and values and a knapsack with a fixed integer size, choose the objects that can fit inside with the most value
  • Minimal Vertex cover - finding the smallest set of vertices such that every edge contains at least one chosen vertice
  • Clique - finding that largest group of people who all know each other
  • Subgraph isomorphism - does one graph contain a subgraph isomorphic to another?
  • Set packing - given a number of sets, what is the maximum number of disjoint sets that can be selected? This is related to set cover, where we are trying to choose sets so that every element is within at least one set
  • Subset sum - Given a set of integers, does some subset sum to 0?

Although many of these problems may seem abstract, many more complicated problems can't be efficiently solved with current techniques, as they are equivalent to one of these.

The problem of NP completeness has received a huge amount of attention. Once you've reduced a problem to NP-complete, you know to give up on an efficient fast algorithm and to start looking at approximations.

  • 1
    $\begingroup$ Also, integer linear-programming, and just about every real-world non-trivial scheduling problem is NP-complete. $\endgroup$ Jul 26, 2010 at 15:50
  • $\begingroup$ Aaaaaand we're forgetting one extremely important one! (see my answer) :) $\endgroup$ Jul 26, 2010 at 16:10
  • $\begingroup$ Additionally, NP completeness is defined in terms of input size, not the size of variables. See this example $\endgroup$
    – Casebash
    Jul 26, 2010 at 23:34
  • $\begingroup$ "Once you've reduced a problem to NP-complete" --- don't you mean once you've reduced an NP-complete problem to your problem? (in polynomial time) $\endgroup$ Oct 28, 2017 at 18:07

Any problem for which a solution (once found) can be quickly verified as a solution is said to be "in NP" (Here, "quickly" means in polynomial-time). Any problem for which a solution can be found quickly is said to be "in P." P is a subset of NP - that is, any problem for which a solution can be quickly found can also be quickly verified.

A problem is NP-complete if it is the hardest problem in NP. Surprisingly, there are many NP-complete problems, which are all equivalent - here, equivalent means that a quick (polynomial-time) solution to any one of them would give you a quick solution to all the rest. Also somewhat surprisingly, a quick solution to any NP-complete problem would also give you a quick solution to any problem in NP.

So is there a quick (polynomial-time) algorithm to solve NP-complete problems? That is the P=NP problem, one of the greatest unsolved problems of our time. However, most sane mathemeticians believe (and hope!) that P≠NP, because proving math-theorems is NP-Complete; so if P=NP, we'd be out of a job! :)

  • $\begingroup$ Proving math theorems is, in general, more than just NP-complete, unless you stay withing the boundaries of propositional logic (and if you do, I wonder what kind of math you're doing). $\endgroup$ Jul 2, 2013 at 20:47

A decision problem D is said to be NP-complete if 1.it belongs to class NP; 2.every problem in NP is polynomially reducable to D.

Reducable means we can convert one instance of problem A in to problem B[NP problem] then it means A is reducable to B.

  • 1
    $\begingroup$ That definition is correct, but not hard to find online. It doesn't really answer the interestng portion of the question. $\endgroup$ Oct 28, 2017 at 10:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .