Layman's Explanation For P=NP?

I think you can explain it to a layman provided that they are interested in puzzles in some way. If they are not, they probably won't care about the explanation in any case.

They should learn by example, not by explaining abstract concepts. Goes like this:

Think you have a box of pieces of paper and each paper has a number written on them. Your task is to find out if there are any duplicates (same number printed on two or more pieces of paper). How do you do it?

At this point, they will probably come up with the simple algorithm. They'll say "I pick one, and see if any of the others are the same. If not, I remove that number from the box and repeat with another number".

At this point, make them think about the cost of adding more numbers to the box. How easy it is to do this with 10 numbers? 100 numbers? 1000 numbers?

If you had to do this with 10 numbers as your job, how pissed would you be if I added one number to the box making it 11 numbers? Probably not very much. It is not really harder to check for 11 numbers compared to 10 numbers.

After going through this example, you then show them a simple problem in the NP class. For instance, the subset sum problem. This is a nice problem to introduce because we can use the previous problem's setting to explain it.

Suppose you have a box of papers with numbers printed on them. Can you find me a set of papers summing to a total of 1234?

How hard is this to do with 5 numbers in the box? How hard with 10? How hard with 100? How would you go about doing it?

Now you'll see they will perceive this as a significantly harder problem (because it is).

Ask the same questions. Suppose your job was to find a result with 10 papers. How pissed would you be if I gave you 11 numbers instead? How does the difficulty change when I add more and more numbers? How does it change compared to the previous problem?


Once all is settled, you explain that scientists classify problems according to their complexity, particularly regarding to how the difficulty of a problem increases when you have more and more inputs.

In the first problem, when you add one more input to the problem, your work increases somewhat proportionally (not really, but it will make sense). If it takes you 1 hour to solve a problem in P, if you add one more input, it might take you 1 hour and 10 minutes. Then one more and it might be 1 hour and 22 minutes. and so on.

For the second problem, adding more and more inputs explodes the time required to solve it. At best, doubles it. Adding one more input essentially means doing everything you did up to that point and doubling all your previous efforts best case. If it takes you 1 hour to solve it, adding one more input means it will now take 2 hours. One more and 4 hours. Add ten more inputs and it will take ~43 days. Eleven more will take ~85 days and twenty more inputs will take 119 years. The complexity of the problem absolutely explodes with the amount of input.

Explain to them that a lot of practical problems we have are similar to the subset sum problem. Actually a lot of the hard problems we have can be simplified into the subset sum problem. Tell them about the Travelling Salesman Problem for instance. If you can find a simple method to solve the subset sum problem quickly, you can essentially solve thousands and thousands of hard and practical problems in one swoop.

P=NP problem deals with this. Might there be an ingenious solution to the subset sum problem such that adding more and more inputs do not add much work to be done to solve it? Even proving it is not possible will solve the P=NP problem. No one has been able to show that this is impossible. No one has been able to show that is it possible either.

The practicality of the problem deals with computational time and work. So it is important for you to explain this to laymen on a plane they can relate to. When they feel they are the ones supposed to be doing the work and spending the time, I believe they will get the main ideas behind it.

And understanding this will pave way to understanding more about complexity theory. For instance Chess is an even harder problem. In subset sum problem, you can check the solution easily, once you grab a bunch of numbers, checking the solution is as easy as summing them. If you are searching the best next move in chess, and evaluate all legal moves while doing so, how do you even check if a move you picked randomly is good or not? Even the "check the random solution" step is a hard problem within itself.

As long as your audience can relate in some basic way (everyone can relate with work and time it takes to complete a job) and they are interested, I think they will be able to get the gist of it.

/r/AskComputerScience Thread