P vs NP for Newbies.

So you must have heard of P vs NP a lot if you are a computer science student, And if you failed to understand it so far like I was till now, here is the explanation in it-can-not-made-more-simpler words


Assuming You had played Super Mario...

You know how sometimes you can get stuck on a stage in Mario, and you spend hours and hours and hours trying to get to the end of the stage, but you just can't seem to figure it out?

But then your clever and more experienced older friend comes over and shows you how to very quickly get past the part you were stuck on. Suddenly, even though you had struggled with it for a long time, it now all becomes clear and seems really easy! 

This problem is an example of what some grownups like to call an "NP-complete" problem. They care about this so much that they'll give you $1,000,000 (Millennium Prize) if you can figure out a fast way to beat any stage in Mario without the help of your older friend!

Grownups have hard problems, too, but they don't have clever older friends to help them with their problems.

This answer is based on the recent paper [1203.1895] Classic Nintendo Games are (NP-)Hard

P vs. NP deals with the gap between computers being able to quickly solve problems vs. just being able to test proposed solutions for correctness.

P and NP are two different kinds of problems. P problems are easy for computers to solve, and NP problems are easy for computers to check answers for, but extremely difficult for computers to solve.
All P problems are NP problems; that is, if it's easy for the computer to solve, it's easy to verify the solution. The P vs NP problem asks: within the class of NP problems, are there problems which are not P, that is, which are not easy for computers to solve?
The problem is that most real-world challenges are NP problems, not P problems. Let's look at a few examples:

• A traveling salesman wants to visit 100 different cities by driving, starting and ending his trip at home. He has a limited supply of gasoline, so he can only drive a total of 10,000 kilometers. He wants to know if he can visit all of the cities without running out of gasoline.
• A farmer wants to take 100 watermelons of different masses to the market. She needs to pack the watermelons into boxes. Each box can only hold 20 kilograms without breaking. The farmer needs to know if 10 boxes will be enough for her to carry all 100 watermelons to market.

All of these problems share a common characteristic that is the key to understanding the nature of P versus NP: In order to solve hard (NP) problems, you have to try all combinations.

image courtesy - www.win.tue.nl

Get 50% off on powerbanks. Now charge your mobile anywhere.