P v NP

How do you decide whether a problem is easy or hard?

One way of answering this question is to come up with an algorithm, a step-by-step recipe, for solving the problem and then seeing how many steps the algorithm involves. If there are many, then the problem is hard, and if there are few, the problem is easy.

Mathematicians have been classifying problems in this way since the beginning of computer science. In the process they have come across two very special classes of problems: the P class and the NP class. The problems in the P class are nice: even though they might be hard to solve for a human, a computer can find a solution in a reasonable amount of time (mathematicians have a precise definition of what they mean by "reasonable"). Problems in the NP class seem to be trickier: nobody has as yet been able to find algorithms that can solve them in a reasonable amount of time. But NP problems do have one redeeming feature. If somebody gives you a possible solution, then at least a computer can check within a reasonable amount of time that it is correct. An example of an NP problem is factoring large numbers into prime numbers, for example, figuring out that

4,719 = 11 x 11 x 13 x 13

This is really difficult to do, but once you have an answer, it's easy to chcek: you simply multiply the factors together and see if you get the right result.

NP problems offer you the chance to become rich and famous over night. The fact that nobody has as yet found good enough algorithms to put them into the friendly P class doesn't mean that these algorithms don't exist. If you happened to find one that works for one of the NP problems then, amazingly, that algorithm could be translated to work for all other NP problems too. You would have shown that all NP problems actually belong into the P class. This would solve the so-called P vs NP problem, one of the hardest open question in modern mathematics; it would earn you one million dollars from the Clay Mathematics Insitute and the admiration of mathematicians the world over!

You would also have made the world a lot less safe, however. The fact that NP problems are so hard to solve is used to encode sensitive information, such as your bank details when you send them over the internet. The problems act like a sort of padlock: you need the answer to unlock the coded message, and since finding the answer from scratch is very hard, nobody else can crack the key. Therefore, finding quicker ways for solving NP problems might lay the world's secrets bare for all to see.