56
$\begingroup$

It is my first question on this site. I am taking a master's course on theory of computation. How you would explain P = NP problem to a 10 year old child and why it has such a monetary reward on it?

Your take?

I will update the question as my head gets clear about it.

Improve this question
$\endgroup$
11
  • 11
    $\begingroup$ My inclination is to close this as being not research level theoretical computer science. $\endgroup$
    – Dave Clarke
    Feb 27, 2011 at 14:32
  • 11
    $\begingroup$ @Dave: It should be answered by research people, so maybe it is adequate to ask it to the place where research people go? $\endgroup$
    – J..y B..y
    Feb 27, 2011 at 15:08
  • 12
    $\begingroup$ I think this is reasonable. There is a famous paper called "How to Explain Zero-Knowledge Protocols to Your Children," which I think would be considered research-level. It's true that it may be hard to select a "best answer," but that is often the case with soft questions. Also, this question could end up being good advertising for the site if sufficiently interesting answers come up...many people might link to the answer given here when asked for an explanation of P vs. NP. $\endgroup$
    – user1338
    Feb 27, 2011 at 19:48
  • 7
    $\begingroup$ but it should really be CW. $\endgroup$
    – Suresh Venkat
    Feb 27, 2011 at 20:52
  • 5
    $\begingroup$ I asked the motivation because the wording of the question gave me the impression that you are not much interested in the answers to your own question (it looked like a way to start a conversation rather than a real question), not because the question is dumb. According to your answer, you seem to have asked this question for the sake of asking a question, and therefore I am not interested in answering it because it will not help you. We have a different culture from Stack Overflow, but that is not relevant now. $\endgroup$
    – Tsuyoshi Ito
    Mar 1, 2011 at 19:33

9 Answers 9

Reset to default
36
$\begingroup$

I use these 3 slides to show why it so hard (impossible?) to come up with a fast algorithm for an NP problem:

Bin packing Bin packing is NP complete 1 Bin packing is NP complete 2

Improve this answer
$\endgroup$
6
  • $\begingroup$ Very easy to understand. $\endgroup$
    – toto
    Feb 28, 2011 at 19:02
  • 4
    $\begingroup$ I think "no easy way" need to be expanded on including scaling as the number of blocks gets bigger $\endgroup$
    – Ian Ringrose
    Mar 2, 2011 at 15:59
  • 3
    $\begingroup$ Very nice example but isn't it called the Rectangle Packing problem in the literature? $\endgroup$
    – Mohammad Al-Turkistany
    Mar 4, 2011 at 21:05
  • 1
    $\begingroup$ @user54609 NP-complete does not mean we can verify that a packing is optimal in polynomial time. NP-complete means we can verify a solution to be feasible in polynomial time (and not consistently find it in polynomial time (unless P==NP)). $\endgroup$
    – Geoffrey De Smet
    May 6, 2014 at 7:28
  • 1
    $\begingroup$ Oh, so the decision problem is "is there a feasible solution". I see. $\endgroup$
    – ithisa
    May 6, 2014 at 7:49
22
$\begingroup$

In this talk Scott Aaronson addresses the question.

TEDxCaltech - Scott Aaronson - Physics in the 21st Century: Toiling in Feynman's Shadow

Warning: Please, do NOT show this talk directly to your grandmother/ 10 year old. why? watch it and you will know. ;-)

EDIT:
Give the kid 8 queens puzzle to solve. Also give him time limit.

If he "finds" a solution then he is one smart kid you can start teaching him CS right away. :)
Else you show him the solution and ask him to "check" if its correct.

$$\begin{array}{|l|l|l|l|} Class & Check & Find & Example \\ \hline \mathsf{P} & Easy & Easy & Multiply \ numbers \\ \mathsf{NP} & Easy & Hard & 8 \ queens \end{array}$$

$\mathsf{P}$ is set of problems to which computer can "find" solution easily.

$\mathsf{NP}$ is set of problems to which computer can't "find" solution easily but can "check" the solution easily.

If we can "check" a solution so easily then why can't we "find" it easily?

What you do in CS is either you solve the problem or prove that no one can.

If someone invents algorithm that makes it easy to "find" solutions for NP problems then the table would look like $$ \begin{array}{|l|l|l|} Class & Check & Find \\ \hline \mathsf{P} & Easy & Easy \\ \mathsf{NP} & Easy & Easy \\ \end{array} $$ and $\mathsf{P} = \mathsf{NP}$.

And if someone proves that no one can find algorithm to "find" solutions for $\mathsf{NP}$ problems then the table remains the same and $\mathsf{P} \neq \mathsf{NP}$.

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ Perhaps you could summarise the essence of Scott's explanation. $\endgroup$
    – Dave Clarke
    Feb 27, 2011 at 17:21
  • 2
    $\begingroup$ I've always been curious what all the P=NP fuss is about, now I do! $\endgroup$
    – Lee Kowalkowski
    Feb 27, 2011 at 22:13
  • $\begingroup$ Since P ∈ NP, maybe clarify that you are talking about the non-P part of NP here. $\endgroup$
    – David
    Feb 18, 2014 at 23:48
  • $\begingroup$ +1 Many great answers in this thread, but this is the only one that even attempts to define what P and NP even mean! $\endgroup$
    – Mark E. Haase
    Apr 13, 2014 at 16:58
  • $\begingroup$ "If we can "check" a solution so easily then why can't we "find" it easily?" --- this question is not answered yet! Otherwise, it is the best answer to me. $\endgroup$
    – user7878
    Apr 15, 2015 at 20:27
19
$\begingroup$

One of the main things people use computers for is searching. Programs like Google are even called "search engines," and they are used millions of times a day. A computer recently beat the humans on Jeopardy because it was able to search through tons of data, super fast.

But some things are hard for even computers to search. Sounds weird, doesn't it? One example is reverse multiplication. Of course if I say "What's 5 times 3?" you can say "15" in a nanosecond, whooosh! But what's the answer to, "What two numbers mutliplied together equal 21?" (Wait for the answer, 7 x 3.) Right! Now, what two numbers multiplied together equal 23? (Wait for the answer, or for frustration.)

The only two numbers multiplied together that equal 23 are 1 and 23 itself. That took some thinking, didn't it? And 23 is a small number. Think if the number were hundreds of digits long. And the thing is, the best programs in the world can't reverse multiplication much better than a 7-year-old might try to, just testing one number, and then the next, and then the next. Computers can do it faster, but we don't really know how to tell a computer to do it smarter. People get PhD's in this stuff, and they only know how to tell computers to do reverse multiplication a little bit smarter.

So maybe there is no smarter way. But maybe there is, and we just haven't found it yet. That's the P/NP problem in a nutshell: if I can recognize an answer right away -- 1 times 23 is 23, duh -- does that help me search for the answer faster? People think it's so important that the person who figures out the answer, yes or no, will win a million dollars.

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ Good one. It probably does not matter that factoring is incidentally a bad example (or is it?). $\endgroup$
    – Raphael
    Mar 1, 2011 at 9:59
  • 4
    $\begingroup$ Factoring was the example Mike Sipser used in his "explain P/NP to the public" video for the Clay Mathematics Institute. I figure if it's good enough for him..... $\endgroup$
    – Aaron Sterling
    Mar 1, 2011 at 14:32
  • 3
    $\begingroup$ Subset sum problem can be explained to pupils who didn't study multiplication yet! $\endgroup$
    – Tegiri Nenashi
    Mar 2, 2011 at 3:44
17
$\begingroup$

I think the P vs. NP problem could be explained very gently in terms of Sudoku. I'm assuming the ten-year-old in question is familiar with Sudoku. I will try to favor simplicity over rigor in my explanation.

Here is my attempt to explain P = NP to a hypothetical ten-year-old:

If you have a Sudoku puzzle that hasn't been finished, and you want to finish it, that can be really hard to do. On the other hand, if your friend finishes the problem and you are good at arithmetic, it's not very hard to check to see if your friend's solution to the puzzle is right.

The P = NP question asks whether or not there is a very fast, step-by-step process for solving a Sudoku puzzle that hasn't been finished yet. The step-by-step process has to be so clear and easy to understand that even a computer can understand it and use it to solve Sudoku puzzles automatically and very fast. If there is such a fast step-by-step process, that would be what mathematicians call a "polynomial time algorithm" (I'll explain what that means when you're older).

In fact, computer scientists and computer programmers have identified a lot of other puzzles and very important problems that are just as hard to solve as Sudoku. It's really important to know if these problems can be solved, because computers could help us do lots of things more quickly if they could. For example, they could help us schedule trains more efficiently, break secret codes, and maybe even build help to build really smart computers that are capable of artificial intelligence.

There would be lots of very good things that would happen if people could solve P = NP. Of course, there would also be some problems, because it would be harder to use secret codes to keep private messages a secret any more.

Most smart mathematicians think that P = NP is not true. In other words, most people think that no one will ever be able to solve really hard Sudoku puzzles quickly. However, no one has ever been able to prove that P is not equal to NP before, so an organization called the Clay Mathematics Institute is offering a prize of one million dollars for the first proof that P = NP is true, or for the first proof that it is false.

As you see, I took the "explain it to a ten-year-old" part a bit literally. :)

Hope this helps.

Improve this answer
$\endgroup$
6
  • $\begingroup$ A very good attempt, although I don't know if a 10 year old will know what a sudoku puzzle is. $\endgroup$
    – chazisop
    Feb 28, 2011 at 9:12
  • 2
    $\begingroup$ @chazisop From experience, I can say that basic versions of sudoku puzzles (i.e. on a 4x4 grid) have been given to kids in grades 3 and 4 as exercises, so it's not an unreasonable assumption. $\endgroup$
    – Bob Fraser
    Feb 28, 2011 at 15:10
  • $\begingroup$ Good take, but: 1) Drop P and NP from the explanation. They hold not meaning. 2) "very fast" creates exactly the wrong intuition. $n^{1000}$ is by no reasonable intuition "very fast", but polynomial. $\endgroup$
    – Raphael
    Mar 1, 2011 at 9:55
  • 1
    $\begingroup$ @Mohsin, You're very welcome. @Raphael, I don't think I need to drop P and NP; a ten year old might just accept my definition of the problem without needing to know what P and NP mean, and I'm not sure how I could explain the problem without referring to it :). Also, I did say I was favoring clarity over complete accuracy...thus, I don't think it's unfair to use "very fast" and "polynomial time" interchangeably. $\endgroup$
    – user1338
    Mar 2, 2011 at 0:31
  • $\begingroup$ My point is that that use of "fast" does not create clarity. Assuming P=NP, maybe the "only" problem is that we are looking for "fast" algorithms for problems which can not be solved "fast", but only polynomially with high degrees. $\endgroup$
    – Raphael
    Mar 2, 2011 at 9:20
8
$\begingroup$

Here is how I explained it to my mother, hopefully it will serve you :)

There are problems for which it is easy to find a solution (P, but less call them "easily solvable"), problems for which it is easy to check if a given solution is correct (NP, but let's call them "easily checkable"), and problems which are neither easily solvable nor easily checkable. For simplicity assume that "Easy" is formally defined, and that each problem has a unique solution.

Now, people have been able to prove (using mathematics) interesting relations between those two notions of "easily solvable" and "easily checkable", such that some problems are not easily solvable, and that some others are not easily checkable. A basic example of such result is that a problem which is easily solvable is also easily checkable: just find its solution and compare it to the solution given.

Tantalizingly enough, for a lot of practical problems (such as deciding if there is a possible assignment of students to professors and classrooms, when there is very little margin) it is not known if there is an "easy" way to solve it, but it is known how to check easily if a solution is correct or not. People tried a lot and failed, then tried to prove that it was not possible and failed as well: they just don't know. Some think that all problems which are easily checkable are easily solvable (we just should think more about it), some think the contrary, that we should not waste our time trying to find easy solutions to these problems.

What we found out is how to show links between problems (e.g. if you know how to go to school, you know how to go to the bakery which is just in front) and easily checkable problems which are linked to all other easily checkable problems (NP-complete, but let's call them "key problems") such that if someone, one day, shows that one of the key problems is easily solved, then all problems which are easily checkable are also easily solvable (i.e. P=NP). On the other hand, if someone show that one of the key problem cannot be easily solvable, then none of the others can be easily solvable either (i.e. P<>NP).

So the question is tantalizing, and relatively important in practice (although some argue that we should rather focus on alternate definitions of "easy"), and people are investing quite a lot of money and time in the debate.

Improve this answer
$\endgroup$
5
$\begingroup$

Michael Sipser explains the P vs NP problem in a highly intuitive way in this video.

Improve this answer
$\endgroup$
2
$\begingroup$

I'm a bit skeptical about the possibility of explaining that problem to a 10 years old, or even to a lay person, without incurring in misrepresentation of the key concepts.

All explanations formulated in terms of "easiness" vs "hardness" of finding vs checking solutions assume the Cobham's thesis, which is arguably false in the general case, and can be considered little more than a rule of thumb at best.

Improve this answer
$\endgroup$
6
  • $\begingroup$ This is not an answer to the question. $\endgroup$
    – Dave Clarke
    Feb 28, 2011 at 13:31
  • $\begingroup$ Why not? The question was "How you would explain P = NP problem to a 10 year old child" and my answer is that a proper explanation that doesn't misrepresent the issue probably doesn't exist. You may disagree with my answer, of course, but why do you claim that it doesn't address the question? $\endgroup$
    – Antonio Valerio Miceli-Barone
    Feb 28, 2011 at 15:17
  • 3
    $\begingroup$ In my opinion, this is a possible answer, although I do not agree. It is true that we cannot mindlessly identify P with something like the “set of the problems which can be solved efficiently in the real world.” However, I do not think that this rules out the possibility of explaining the P=?NP problem to a ten-year-old child at an intuitive level. For example, children of ten year old or so learn the area of a circle. Any rigorous treatment of area requires great care, but that does not rule out the possibility of teaching the concept of area at an intuitive level in a useful way. $\endgroup$
    – Tsuyoshi Ito
    Feb 28, 2011 at 16:41
  • $\begingroup$ Identifying the complexity class $\mathbf{P}$ with feasible problems is a simplification/idealization similar to those used in other sciences like physics, you can say that even the asymptotic analysis is misleading since the constants can be very large and the algorithm would be infeasible to run, that might be the case, but these concepts are good enough approximation for many tasks and are useful in practice. The question is giving an intuition about these concepts to non-experts, I am not sure if a first introductory explanation of them to a non-expert need to be completely accurate or $\endgroup$
    – Kaveh
    Feb 28, 2011 at 22:16
  • 1
    $\begingroup$ [continued] go into details and mention the shortcomings of the model. It is just an abstract simplified mathematical model that tries to capture some aspects of an intuitive notion. According to current physicists, the Newtonian physics is fundamentally incorrect and does not make right predications about reality in some domains, but it works quite well for most engineering tasks. Any abstract mathematical model of an intuitive/real concept is just a model, Cobham's thesis about identifying feasible decision algorithms with $\mathbf{P}$ is no different. $\endgroup$
    – Kaveh
    Feb 28, 2011 at 22:16
0
$\begingroup$

And here is my take at the problem.

Kido!

You know we face many problems in our life. You can say challenges. Some are hard some are easier. For example, you often need to add two numbers. And last evening, we were on the chess board and we had to win against our neighbour. Well, adding two numbers is a simple and straight problem with limited steps involved. Such problems are called P class problems because there are many many problems that are pretty straightforward with discrete steps that are to be repeated over and over to get a solution.

On the ohter hand, last night on our chest game, what would be the best strategy to win the game? We could move the first pawn one step, or the second pawn one step, or we could move second pawn two steps and first pawn one step so you see there are lots and lots of possibilities. But is there a way for us or a recipie that gives us a complete ordered sets of moves that yield a best and to a checkmate? So you see it is quit hard because there are so many possibilites one each step. Billions and Billions as Carl Sagan says.

But dear what if I tell you all the board positions and ask you is it a checkmate? Surely you will be able to quickly tell within few examinations whether there are any legal moves left for the king.

So such problems which are hard to solve but if their solution is easily verifiable in few simple steps, they are called NP problems.

Now you ask what P = NP means? Actually this question means that is there a way that we can find a simpleler solutuion for finding the best strategy or ordered list of moves for a chess game without going through all the billions of possibilities just like we do for a simple addition? This simple quesiton is yet unanswered. We have neither any proof for it's truth or for rejection but if we do, it will be breakthrough. If it comes out to be true, our civilization might get to solve very complex probelms by turning them into P class problems. People will be able to break passwords wihtin seconds, messages will be decrypted and much much more and that is why this problem is considered to be one of the most important probelms of the millenium.

Improve this answer
$\endgroup$
5
  • $\begingroup$ It might be worth tightening the text. Have you tried reading this aloud? $\endgroup$
    – András Salamon
    Mar 2, 2011 at 10:02
  • $\begingroup$ Everything should't be tightened like mathematical definitions I think. $\endgroup$
    – Mohsin Hijazee
    Mar 2, 2011 at 14:57
  • $\begingroup$ If you tighten the text too much, normal peole will not have enough "space" to understand one concept before you move onto the next concept. $\endgroup$
    – Ian Ringrose
    Mar 2, 2011 at 17:18
  • $\begingroup$ What kind of decision-problems are known to be NP-complete an $n\times n$ chessboard? It looks like most of problems considered are much harder: mathoverflow.net/questions/27944/…. $\endgroup$
    – Juan Bermejo Vega
    Mar 2, 2012 at 11:17
  • $\begingroup$ This link is maybe more clear than the previous: cstheory.stackexchange.com/questions/6563/… $\endgroup$
    – Juan Bermejo Vega
    Mar 2, 2012 at 11:30
0
$\begingroup$

winning strategies for various classic board games eg battleship or (more recently) video games have been proven NP complete & this is an excellent way/angle to present/describe some of the core theory to newbies.

battleship as a NP complete decision problem Merlijn Sevenster ICGA journal sep 2004

minesweeper is NP complete FAQ by mathematician RW Kaye. Spring 2000 issue of the Mathematical Intelligencer (volume 22 number 2, pages 9--15)

Gaming is a hard job, but someone has to do it! arxiv paper by Giovanni Viglietta. analyzes computational complexity of Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble 3, and Starcraft.

Pacman is hard extreme tech mag article on above paper

Improve this answer
$\endgroup$
1

Not the answer you're looking for? Browse other questions tagged or ask your own question.