How to Play:

Jump pegs by clicking on a peg then clicking on the hole you wish to jump it to. When a peg is jumped, it is automatically removed. Pegs can only be removed by jumping them. Try to remove all of the pegs! Click below for some more information.

# P and NP

Computer scientists like to classify how fast their algorithms will run. We like to call the various speeds, complexity classes. For one such complexity class, the number of ways to solve the problem increases exponentially with the input size. We call these problems NP problems. For NP problems, we cannot find a solution efficiently. The other complexity class refers to problems where the speed is some polynomial factor of the input size. These are referred to as P problems or problems that we can solve easily.

# P ≠ NP

What about the P ≠ NP game? If P ≠ NP then in order to ensure that the next step we are taking will lead to a correct solution, we must test all possible steps in the future. Testing all possible steps in the future will take a considerable amount of time. This make it more difficult to find the solution.

# P = NP

So what if P = NP! This suggests that all of the problems currently catagorized in the NP complexity class can also be placed in the P complexity class. This means that problems that we currently don't have efficient solutions for, can really be solved efficiently. For example, in the game above, if P = NP, then we can efficiently know what move to make next in order to win the game!