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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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:
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.
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! :)