**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.