Question: What is an NP-complete problem? Why is it such an important topic in computer science?

Answer: 
If you're looking for an example of an NP-complete problem then I suggest you take a look at [3-SAT](http://en.wikipedia.org/wiki/Boolean_satisfiability_problem).

The basic premise is you have an expression in [conjunctive normal form](http://en.wikipedia.org/wiki/Conjunctive_normal_form), which is a way of saying you have a series of expressions joined by ORs that all must be true:

```
(a or b) and (b or !c) and (d or !e or f) ...

```

The 3-SAT problem is to find a solution that will satisfy the expression where each of the OR-expressions has exactly 3 booleans to match:

```
(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

```

A solution to this one might be (a=T, b=T, c=F, d=F). However, no algorithm has been discovered that will solve this problem in the general case in polynomial time. What this means is that the best way to solve this problem is to do essentially a brute force guess-and-check and try different combinations until you find one that works.

What's special about the 3-SAT problem is that ANY NP-complete problem can be reduced to a 3-SAT problem. This means that if you can find a polynomial-time algorithm to solve this problem then you get [$1,000,000](http://en.wikipedia.org/wiki/Millennium_Prize_Problems), not to mention the respect and admiration of computer scientists and mathematicians around the world.
The definitions for NP complete problems above is correct, but I thought I might wax lyrical about their philosophical importance as nobody has addressed that issue yet.

Almost all complex problems you'll come up against will be NP Complete. There's something very fundamental about this class, and which just seems to be computationally different from easily solvable problems. They sort of have their own flavour, and it's not so hard to recognise them. This basically means that any moderately complex algorithm is impossible for you to solve exactly -- scheduling, optimising, packing, covering etc.

But not all is lost if a problem you'll encounter is NP Complete. There is a vast and very technical field where people study approximation algorithms, which will give you guarantees for being close to the solution of an NP complete problem. Some of these are incredibly strong guarantees -- for example, for 3sat, you can get a 7/8 guarantee through a really obvious algorithm. Even better, in reality, there are some very strong heuristics, which excel at giving great answers (but no guarantees!) for these problems.

Note that two very famous problems -- graph isomorphism and factoring -- are not known to be P or NP.