NP-complexity for Dummies (like me)

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 Polynomial 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 Non-deterministic Polynomial, 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!

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s