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

Answer: 
What is [NP](https://en.wikipedia.org/wiki/NP_(complexity))?
------------------------------------------------------------

NP is the set of all [decision problems](https://en.wikipedia.org/wiki/Decision_problem) (questions with a yes-or-no answer) for which the 'yes'-answers can be ***verified*** in polynomial time (O(nk) where *n* is the problem size, and *k* is a constant) by a [deterministic Turing machine](http://en.wikipedia.org/wiki/Deterministic_Turing_machine). Polynomial time is sometimes used as the definition of *fast* or *quickly*.

What is [P](https://en.wikipedia.org/wiki/P_(complexity))?
----------------------------------------------------------

P is the set of all decision problems which can be **solved** in *polynomial time* by a *deterministic Turing machine*. Since they can be solved in polynomial time, they can also be verified in polynomial time. Therefore P is a subset of NP.

What is [NP-Complete](https://en.wikipedia.org/wiki/NP-complete)?
-----------------------------------------------------------------

A problem x that is in NP is also in NP-Complete *if and only if* every other problem in NP can be quickly (ie. in polynomial time) transformed into x.

In other words:

1. x is in NP, and
2. Every problem in NP is [*reducible*](https://en.wikipedia.org/wiki/Reduction_(complexity)) to x

So, what makes *NP-Complete* so interesting is that if any one of the NP-Complete problems was to be solved quickly, then all *NP* problems can be solved quickly.

See also the post [What's "P=NP?", and why is it such a famous question?](https://stackoverflow.com/questions/111307/whats-pnp-and-why-is-it-such-a-famous-question)

What is [NP-Hard](https://en.wikipedia.org/wiki/NP-hard)?
---------------------------------------------------------

NP-Hard are problems that are at least as hard as the hardest problems in NP. Note that NP-Complete problems are also NP-hard. However not all NP-hard problems are NP (or even a decision problem), despite having `NP` as a prefix. That is the NP in NP-hard does not mean *non-deterministic polynomial time*. Yes, this is confusing, but its usage is entrenched and unlikely to change.
NP-Complete means something very specific and you have to be careful or you will get the definition wrong. First, an NP problem is a yes/no problem such that

1. There is polynomial-time proof for every instance of the problem with a "yes" answer that the answer is "yes", or (equivalently)
2. There exists a polynomial-time algorithm (possibly using random variables) that has a non-zero probability of answering "yes" if the answer to an instance of the problem is "yes" and will say "no" 100% of the time if the answer is "no." In other words, the algorithm must have a false-negative rate less than 100% and no false positives.

A problem X is NP-Complete if

1. X is in NP, and
2. For any problem Y in NP, there is a "reduction" from Y to X: a polynomial-time algorithm that transforms any instance of Y into an instance of X such that the answer to the Y-instance is "yes" if and only if the answer X-instance is "yes".

If X is NP-complete and a deterministic, polynomial-time algorithm exists that can solve all instances of X correctly (0% false-positives, 0% false-negatives), then any problem in NP can be solved in deterministic-polynomial-time (by reduction to X).

So far, nobody has come up with such a deterministic polynomial-time algorithm, but nobody has proven one doesn't exist (there's a million bucks for anyone who can do either: the is the [P = NP problem](http://en.wikipedia.org/wiki/P_%3D_NP_problem)). That doesn't mean that you can't solve a particular instance of an NP-Complete (or NP-Hard) problem. It just means you can't have something that will work reliably on all instances of a problem the same way you could reliably sort a list of integers. You might very well be able to come up with an algorithm that will work very well on all practical instances of a NP-Hard problem.