What is P=NP?

You may have heard this term floating around the computer science ether, and rightly so; a resolution to the problem could have huge implications for the world, not just the world of computer science!

A short explanation of what P=NP is:

1. A yes or no problem is in P [Polynomial time] if the answer can be computed in polynomial time.
2. A yes-or-no problem is in NP [Non-deterministic Polynomial time] if a yes answer can be verified in polynomial time.

After some thought, it is apparent that a problem that is P must also be NP. Given a potential answer for a problem in P, we can verify the answer by simply recalculating the answer. For example the question 7 x 17 is equal to 119. This problem is easy to calculate since we can quickly find the value of 7 x 17.

But it becomes much harder when we wish to verify, for example, that X is possibly 7 for X * Y = 19. Less obvious, and much more difficult to answer, is whether all problems in NP are in P. Does the fact that we can verify an answer in polynomial time mean that we can compute that answer in polynomial time?

There are a large number of important problems that are known to be NP-complete [basically, if any these problems are proven to be in P, then all NP problems are proven to be in P]. If P = NP, then all of these problems will be proven to have an efficient [polynomial time] solution.

Why is any of this so important though? It’s because many of the problems we know to be in NP or NP-complete are problems that we actually want to solve. and the diverse NP-complete problems are all polynomial time related to one another so if we should ever learn a feasible means of solving any of them, we would have feasible means for all of them. The result of this would be extraordinary, something like a second industrial revolution! A computational revolution. It would be as though we suddenly had a huge permanent increase in computational power, allowing us to solve an enormous array of practical problems heretofore out of our computational reach. The P vs. NP question is important in part because of this tantalising possibility.

However! Most scientists and even more so, computer scientists believe that P!=NP. However, no proof has yet been established for either P = NP or P!=NP. If anyone provides a proof either way for the P = NP problem, they will not only get worldwide recognition and have solved one of the most argued questions in computer science; they will also receive $1 million since the P versus NP problem is one of the seven Millennium Prize Problems and was officially stated by Stephen Cook and set by the Clay Mathematics Institute.