Despite all the computational theory that I have studied over the years, the definitions of P, NP, NP-hard, and NP-complete have always been fuzzy in my mind. But I think I’m finally getting the hang of it, and I want to write it out (in overly-simplistic language) before I forget (again)!

**P**-problems are those that can be *solved in ***P***olynomial time*. That doesn’t mean they’re easy, necessarily – they may be O(n^2), or even O(n^Googol), but they’re *do-able*.

Then there are the *other* problems. The * hard* ones. The ones (for example) that take an exponential amount of time to solve – like cracking passwords with brute force.

There are a lot of these hard problems that nobody has ever found a polynomial-time algorithm for. Doesn’t mean one doesn’t exist, it just hasn’t yet been discovered. Now *some* of these problems have a particular characteristic that, although they can’t be *solved* quickly (yet), they can at least be* verified* quickly. That means that if some wizard said, “Here’s the *answer* to this particular problem”, you could quickly do some math and say, “Yep. He’s correct. That’s the answer all right.” (It might take magic to solve your password, but I can *check* one of my guesses instantaneously.)

Problems of this sort (with easy-to-test answers) are known as **NP**. (Important note: “NP” does *not* stand for “Non-Polynomial”. As a matter of fact, *all* **P** problems are by necessity also **NP** – they have easy-to-test answers. **NP** actually stands for **N**on-deterministic **P**olynomial, for reasons that aren’t really necessary to understand.)

OK, so now we have this set of **NP** problems (which includes all the P problems, and many others that may or may not be in P, but appear so hard that we doubt they are in P). Now it just so happens that some brainy dudes started studying all these NP problems that seemed outside of P, and they noticed a curious detail about them: They all turn out to be “equivalently” hard. (That statement is not *precisely *accurate, but I’ll clarify shortly.) So, for all of these problems (even the really-really hard ones that would take a billion eons to solve with current algorithms), it turns out that if you can find a way to solve any *one* of them quickly, you could solve *all* of them quickly! If you find a key that unlocks one of them, that key can be used to unlock all of them! So, the brainiacs have given this quirky set of quasi-equivalent problems a special name: they call them **NP-complete**. Technically put: any problem in NP can be “reduced” to any problem in NP-Complete; therefore, this set is equivalent to the *hardest* problems in NP.

There is another class of problems that are even “*harder” *than NP-complete. They are the ones that are outside of NP altogether (in other words, even their *answers* are not easily verifiable). However, even some of these (or perhaps all of them; I’m not clear on this part yet) can be mapped or “reduced” to the NP-complete problems. These are called the **NP-hard** problems. That is: they’re not in NP, but they are technically * no harder* than the ones that are.

SOOO, if someone wakes up tomorrow and discovers an efficient (polynomial time) solution to just *one* of the NP-complete problems, the entire fortress of NP-complete problems will collapse and they will all be “solved” (or, rather, “solvable”). So you say, “well of course, that’s impossible; that could never happen.” And you’d probably be right. But here’s the thing: NO ONE HAS EVERY PROVEN THAT TO BE TRUE! Despite decades of trying by the brightest of the bright, and a $1 million dollar reward. You could also win the $1million by proving that even ONE of the NP-complete problems is for sure NOT in P, but nobody has been able to do that either.

So what are you waiting for? Get busy! Go out there and win a million dollars!