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

Answer: 
NP-Complete is a class of problems. 

The class **`P`** consists of those problems that are solvable in **polynomial time**. For example, they could be solved in O(nk) for some constant k, where *n* is the size of the input. Simply put, you can write a program that will run in *reasonable* time.

The class **`NP`** consists of those problems that are **verifiable** in polynomial time. That is, if we are given a potential solution, then we could check if the given solution is correct in polynomial time.

Some examples are the Boolean Satisfiability (or **SAT**) problem, or the Hamiltonian-cycle problem. There are many problems that are known to be in the class NP. 

**`NP-Complete`** means the problem is **at least** as hard as any problem in NP.

It is important to computer science because it has been proven that any problem in NP can be **transformed** into another problem in NP-complete. That means that a solution to any one NP-complete problem is a solution to all NP problems.

Many algorithms in security depends on the fact that no known solutions exist for NP hard problems. It would definitely have a significant impact on computing if a solution were found.
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.