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.
We need to separate algorithms and problems. We write algorithms to solve problems, and they scale in a certain way. Although this is a simplification, let's label an algorithm with a 'P' if the scaling is good enough, and 'NP' if it isn't.

It's helpful to know things about the problems we're trying to solve, rather than the algorithms we use to solve them. So we'll say that all the problems which have a well-scaling algorithm are "in P". And the ones which have a poor-scaling algorithm are "in NP".

That means that lots of simple problems are "in NP" too, because we can write bad algorithms to solve easy problems. It would be good to know which problems in NP are the really tricky ones, but we don't just want to say "it's the ones we haven't found a good algorithm for". After all, I could come up with a problem (call it X) that I think needs a super-amazing algorithm. I tell the world that the best algorithm I could come up with to solve X scales badly, and so I think that X is a really tough problem. But tomorrow, maybe somebody cleverer than me invents an algorithm which solves X and is in P. So this isn't a very good definition of hard problems.

All the same, there are lots of problems in NP that nobody knows a good algorithm for. So if I could *prove* that X is a certain sort of problem: one where a good algorithm to solve X could *also* be used, in some roundabout way, to give a good algorithm for *every* other problem in NP. Well now people might be a bit more convinced that X is a genuinely tricky problem. And in this case we call X NP-Complete.