What are NP-complete problems and why are they so important?

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·n^k 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:

• 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.

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