Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 16 down vote accepted

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.

share|improve this answer
5  
You mean "only known algorithms for NP complete problems" –  Simon Nickerson Jul 26 '10 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.

share|improve this answer
1  
Also, integer linear-programming, and just about every real-world non-trivial scheduling problem is NP-complete. –  BlueRaja - Danny Pflughoeft Jul 26 '10 at 15:50
    
Aaaaaand we're forgetting one extremely important one! (see my answer) :) –  BlueRaja - Danny Pflughoeft Jul 26 '10 at 16:10
    
Additionally, NP completeness is defined in terms of input size, not the size of variables. See this example –  Casebash Jul 26 '10 at 23:34

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! :)

share|improve this answer
    
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). –  Johannes Kloos Jul 2 '13 at 20:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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