P vs. NP

A Question of Complexity

The Clay Mathematics Institute in May of 2000 announced 7 Millennium Prize Problems, mathematical problems that have stubbornly resisted solution over the years. Each of these problems is associated with a million dollar prize for the person that solves it. One of these problems is P vs. NP, and is of great concern to computer scientists. P and NP are complexity classes, a way of organizing problems that we wish to solve, and the problem in question is to prove either that they are equal or not equal.

P problems

Problems in the P category can be solved in polynomial time. This means that the time is takes to solve a problem is proportional to some polynomial of the size of the input. An example would be finding someone's name in the phone book. A good way to do this would be to split the phone book in half and only keep the half that the person's name is in. You then split the the kept half in half, and so on such that you only keep the half that the name is in. Even for a phone book with 10,000 entries, it would only take at most 14 splits to reach the target entry. This problem and other P problems are ones that computers are very quick at solving, and we like them very much.

NP problems

NP problems on the other hand are not so nice. These problems cannot (as far as we know) be solved directly in polynomial time. But, if we are given a solution to an NP problem, it would be very easy to check that the solution is correct. The example used in the Numb3rs episode of an NP problem concerned the computer game Minesweeper. Other examples include the Traveling Salesman Problem and various aspects of Tetris such as maximizing the number of cleared rows or minimizing the height of the blocks.

The Big Question

Now the problem that mathematicians are trying to figure out is this: Does P equal NP? If this were true, the there would be a way to transform every NP problem into one that is solvable in polynomial time. This would mean that certain areas of cryptography would be rendered useless, but it would also mean that given any true theorem, we could find a corresponding proof in polynomial time. Although most computer scientists generally believe that N does not equal NP, the hunt is still on for a proof either way.

Math in TV

The P vs. NP problem is mentioned in an episode of the hit CBS television series Numb3rs. To read about this and another one of the Millennium Prize Problems visit "Math Could Make You Rich!"