Episode 7: P vs. NP

Mmm...the world of computer science; where mathematics meets application in the purest sense.

A little fact about me: I don't really like applied math at all. I have nothing against it, that specific area of math just isn't for me. I seem to lose interest as soon as the math I'm learning has an application. However, computer science is the only application of mathematics where I don't totally lose interest. I think it's because the "application" is just more mathy goodness :)

So! The biggest question in the world of computer science is:

Does P=NP?

No one knows, and there will be some big bucks awarded to whoever finds out what the answer is.

But what does it mean? What is P? What is NP? And who cares if they are equal or not?

It's actually not as scary as it sounds (in general, math is not as scary as it sounds...except for RFM, that's for sure scary...).

Ok, so basically P represents the set of all problems that can be found in polynomial time, and NP represents the set of all problems whose solutions can be verified in polynomial time.

Polynomial time just means that the time needed to find the solution has a polynomial relationship with the size of the problem.

The question, does P=NP? asks whether all problems which can be solved in polynomial time, can also be verified in polynomial time.


So what's the big deal? Why does it matter if they're equal or not?

Well, if P=NP then it would transform mathematics, and the world. It would mean that computers could find proofs of theorems which have proofs of reasonable length (so would mathematicians be out of a job?). It would also cause a lot of problems in security on the internet. A lot (ok, actually ALL) security systems on the internet are running on the fact that P doesn't equal NP. If it turned out they did, well, let's just say: massive chaos.

If P≠NP then it wouldn't be as exciting (and definitely not as surprising), but it would still be useful to mathematicians and computer scientists alike. It would allow people to show, formally, that many common problems just can't be solved efficiently. This result would allow researchers to focus their attention on more practical problems. The general belief is that P≠NP.


So why is this question so hard? Why can't anyone figure it out?

The answer to this question is actually quite simple: we don't know enough, and our knowledge base is too small. Most sciences who have studied this problem think that we just don't have the right tools and proof methods right now in order to approach this and solve this correctly.

That sounds simple enough, right? Humans just aren't smart enough. Yet.

It just needs a fresh look, and maybe some new ideas. Who knows, maybe you'll solve it :)