Explain Like I'm Five

Some problems get harder to do on bigger numbers. Like breaking a number into factors; the bigger the number, the harder it is to find the factors. Contrast this with, say, telling whether the number is even, which is easy even for very very large numbers.

There is a certain measure of how quickly problems get harder with bigger numbers called Polynomial Time; this is the P in P, NP, etc. I will omit the details of what polynomial time means exactly because if you don't know from the name, then the details aren't particularly important. It's just a certain measure of how quick or hard the problem is to solve.

So for the various types of problems:

• P - The list of problems that can be solved quickly. For example, telling if a number is even.
• NP - The list of problems where you can check the answer quickly. For example, factoring a number.
• NP Complete - A list of special NP problems where we know how to "translate" any NP problem into one of these NP complete problems. Solving a Peg Solitaire game is NP complete.
• NP Hard - Problems at are as hard as NP Complete or harder. The travelling salesman problem (finding the shortest route that visits a list of cities) and the halting problem (figuring out if a computer program will get stuck in an infinite loop) are NP Hard.