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

<p><img src="https://i.sstatic.net/MeDkj.png" alt="Bin packing">
<img src="https://i.sstatic.net/eNbe7.png" alt="Bin packing is NP complete 1">
<img src="https://i.sstatic.net/Bhtsx.png" alt="Bin packing is NP complete 2"></p>

CC BY-SA 3.0
2014-05-05T14:28:25.267Z
Necropost, and call me horribly stupid and retarded, but how is this problem in NP? How can you verify that a given packing is the optimal packing in polynomial time?
ithisa
CC BY-SA 3.0
2014-05-06T07:28:24.470Z
@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)).
Geoffrey De Smet
CC BY-SA 3.0
2014-05-06T07:49:30.157Z
Oh, so the decision problem is "is there a feasible solution". I see.
ithisa
CC BY-SA 2.5
2011-02-28T19:02:35.153Z
Very easy to understand.
toto
CC BY-SA 2.5
2011-03-02T15:59:52.710Z
I think "no easy way" need to be expanded on including scaling as the number of blocks gets bigger
Ian Ringrose
CC BY-SA 2.5
2011-03-04T21:05:51.737Z
Very nice example but isn't it called the Rectangle Packing problem in the literature?
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-28T09:55:47.323Z
2011-02-28T09:55:47.323Z
Geoffrey De Smet
<p>In this talk <a href="https://cstheory.stackexchange.com/users/1575/scott-aaronson">Scott Aaronson</a> addresses the question. </p>

<p><strong><a href="http://www.youtube.com/watch?v=SczraSQE3MY" rel="nofollow noreferrer">TEDxCaltech - Scott Aaronson - Physics in the 21st Century: Toiling in Feynman's Shadow</a></strong></p>

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

<p><strong>EDIT:</strong><br>
Give the kid <a href="http://en.wikipedia.org/wiki/Eight_queens_puzzle" rel="nofollow noreferrer"><strong>8 queens puzzle</strong></a> to solve. Also give him time limit. </p>

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

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

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

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

<blockquote>
  <p>If we can "check" a solution so easily then why can't we "find" it easily? </p>
</blockquote>

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

<p>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 &amp; Check &amp; Find \\
\hline
\mathsf{P}  &amp; Easy  &amp; Easy \\
\mathsf{NP} &amp; Easy  &amp; Easy \\
\end{array}
$$
and $\mathsf{P} = \mathsf{NP}$. </p>

<p>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}$. </p>

CC BY-SA 2.5
2011-02-27T17:21:16.717Z
Perhaps you could summarise the essence of Scott's explanation.
Dave Clarke
CC BY-SA 2.5
2011-02-27T22:13:33.343Z
I've always been curious what all the P=NP fuss is about, now I do!
Lee Kowalkowski
CC BY-SA 3.0
2014-02-18T23:48:45.053Z
Since P ∈ NP, maybe clarify that you are talking about the non-P part of NP here.
David
CC BY-SA 3.0
2014-04-13T16:58:02.657Z
+1 Many great answers in this thread, but this is the only one that even attempts to define what P and NP even mean!
Mark E. Haase
CC BY-SA 3.0
2015-05-19T16:35:35.577Z
@BROY If I could answer that I would be millionaire and win Turing award or two!
Pratik Deoghare
CC BY-SA 3.0
2011-02-27T17:19:40.510Z
2011-08-14T07:19:33.183Z
2017-04-13T12:32:28.117Z
Pratik Deoghare
<p>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.</p>

<p>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.)</p>

<p>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 <em>faster</em>, but we don't really know how to tell a computer to do it <em>smarter</em>.  People get PhD's in this stuff, and they only know how to tell computers to do reverse multiplication a little bit smarter.</p>

<p>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 <em>search for</em> 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.</p>

CC BY-SA 2.5
2011-03-01T09:59:28.417Z
Good one. It probably does not matter that factoring is incidentally a bad example (or is it?).
Raphael
CC BY-SA 2.5
2011-03-01T14:32:48.570Z
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.....
Aaron Sterling
CC BY-SA 2.5
2011-03-02T03:44:05.643Z
Subset sum problem can be explained to pupils who didn't study multiplication yet!
Tegiri Nenashi
CC BY-SA 2.5
2011-02-28T14:54:47.667Z
2011-02-28T14:54:47.667Z
Aaron Sterling
<p>Here is how I explained it to my mother, hopefully it will serve you :) </p>

<p>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.</p>

<p>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. </p>

<p>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.</p>

<p>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&lt;>NP).</p>

<p>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. </p>

CC BY-SA 2.5
2011-02-27T15:07:38.173Z
2011-02-27T15:12:40.853Z
2011-02-27T15:12:40.853Z
J.y B.y
<p>Michael Sipser explains the P vs NP problem in a highly intuitive way in <a href="http://www.youtube.com/watch?v=msp2y_Y5MLE" rel="noreferrer">this video</a>.</p>

CC BY-SA 3.0
2012-03-01T20:08:49.177Z
2012-03-01T20:08:49.177Z
Shitikanth
<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-02-28T13:31:54.740Z
This is not an answer to the question.
Dave Clarke
CC BY-SA 2.5
2011-02-28T15:17:12.700Z
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?
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2011-02-28T16:41:24.853Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-28T22:16:07.903Z
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
Kaveh
CC BY-SA 2.5
2011-02-28T22:16:24.733Z
[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.
Kaveh
CC BY-SA 2.5
2011-03-01T23:59:16.927Z
I may agree with this answer, depending on what the asker meant by “explain the P=NP problem.”  I realized that the question was very vague.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-28T13:25:00.553Z
2011-02-28T13:25:00.553Z
Antonio Valerio Miceli-Barone
<p>winning strategies for various classic board games eg battleship or (more recently) video games have been proven NP complete &amp; this is an excellent way/angle to present/describe some of the core theory to newbies.</p>

<p><a href="http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf" rel="nofollow">battleship as a NP complete decision problem</a> Merlijn Sevenster ICGA journal sep 2004</p>

<p><a href="http://web.mat.bham.ac.uk/R.W.Kaye/minesw/FAQ.htm" rel="nofollow">minesweeper is NP complete FAQ</a> by mathematician RW Kaye. Spring 2000 issue of the Mathematical Intelligencer (volume 22 number 2, pages 9--15)</p>

<p><a href="http://arxiv.org/abs/1201.4995" rel="nofollow">Gaming is a hard job, but someone has to do it!</a> 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.</p>

<p><a href="http://www.extremetech.com/gaming/115677-pac-man-is-np-hard-same-as-travelling-salesman-problem" rel="nofollow">Pacman is hard</a> extreme tech mag article on above paper</p>

CC BY-SA 3.0
2013-02-27T17:36:47.453Z
see also [A SURVEY OF NP-COMPLETE PUZZLES](http://red.cs.nott.ac.uk/~gxk/papers/icga2008_preprint.pdf) by Kendall, Parkes, Spoerer, and [Playing games with algorithms: Algorithmic Combinatorial Game Theory](http://arxiv.org/abs/cs.CC/0106019) by Demaine and Hearn
vzn
CC BY-SA 3.0
2012-01-27T16:12:40.993Z
2012-01-27T16:12:40.993Z
vzn
<p>And here is my take at the problem.</p>

<p>Kido!</p>

<p>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.</p>

<p>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.</p>

<p>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. </p>

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

<p>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. </p>

CC BY-SA 3.0
2012-03-02T11:17:37.967Z
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: http://mathoverflow.net/questions/27944/do-there-exist-chess-positions-that-require-exponentially-many-moves-to-reach.
Juan Bermejo Vega
CC BY-SA 3.0
2012-03-02T11:30:10.073Z
This link is maybe more clear than the previous: http://cstheory.stackexchange.com/questions/6563/what-is-the-computational-complexity-of-solving-chess
Juan Bermejo Vega
CC BY-SA 2.5
2011-03-02T10:02:33.610Z
It might be worth tightening the text.  Have you tried reading this aloud?
András Salamon
CC BY-SA 2.5
2011-03-02T14:57:30.300Z
Everything should't be tightened like mathematical definitions I think.
Mohsin Hijazee
CC BY-SA 2.5
2011-03-02T17:18:59.927Z
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.
Ian Ringrose
CC BY-SA 2.5
2011-03-01T18:57:25.663Z
2011-03-01T18:57:25.663Z
Mohsin Hijazee
<p>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?</p>

<p>Your take?</p>

<p>I will update the question as my head gets clear about it.</p>

CC BY-SA 2.5
2011-02-27T14:32:23.800Z
My inclination is to close this as being not **research level** theoretical computer science.
Dave Clarke
CC BY-SA 2.5
2011-02-27T15:08:33.710Z
@Dave: It should be answered by research people, so maybe it is adequate to ask it to the place where research people go?
J.y B.y
CC BY-SA 2.5
2011-02-27T15:32:35.110Z
This is not the first time I've heard this issue. I believe it spans from a belief attributed to Feynman, that you can say we have understood something completely only if we can phrase it in a way that an elementary school student can comprehend it. This principle applied to $P=NP$ is very interesting, but I believe it is more suitable for a communication with a discussion format, rather than question answering, so that after a while a community consensus is formed, rather than electing an answer as best , which can be far from optimal.
chazisop
CC BY-SA 2.5
2011-02-27T20:25:43.793Z
The community decision seems to be to keep the question open. It'll be good to get some fresh young minds looking at the problem.
Dave Clarke
CC BY-SA 2.5
2011-02-27T20:52:36.017Z
but it should really be CW.
Suresh Venkat
CC BY-SA 2.5
2011-03-01T12:17:38.627Z
What is the motivation of this question?  And what do you mean by “explaining the P=NP problem”?  For example, if you somehow have to explain the _precise formulation_ of the P=NP problem so that a ten-year-old child can understand it, then you are almost surely out of luck.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-01T18:44:18.337Z
If a thing cannot be explained in five minutes, either it is not well understoodd it or it doesn't work. The culture of stackoverflow sites have been to allow dumb questions as well and there is no mention that this is a site only for the research level. Research level wont resort to QA sites I'm sure of that. Science of one century is the common sense of the next. If this site stands for hundred years, may be we have the earliest layman explanation of the problem?
Mohsin Hijazee
CC BY-SA 2.5
2011-03-01T19:33:59.540Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-14T07:37:49.400Z
This is a cool question.  I hope that the great answers are recognized as they are added over time.
Matt M.
CC BY-SA 3.0
2012-01-27T16:00:40.437Z
see also [everyday encounters with NP complete problems](http://cstheory.stackexchange.com/questions/446/everyday-encounters-with-np-complete-problems)
vzn
<cc.complexity-theory><soft-question><teaching><p-vs-np>
Explain P = NP problem to 10 year old
Mohsin Hijazee
# Explain P = NP problem to 10 year old

(Asked by: username_0 on 2011-02-27)

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.

**Tags:** cc.complexity-theory, soft-question, teaching, p-vs-np
> **Comments:**
> **username_1**: My inclination is to close this as being not **research level** theoretical computer science.  
> **username_2**: @Dave: It should be answered by research people, so maybe it is adequate to ask it to the place where research people go?  
> **username_3**: This is not the first time I've heard this issue. I believe it spans from a belief attributed to Feynman, that you can say we have understood something completely only if we can phrase it in a way that an elementary school student can comprehend it. This principle applied to $P=NP$ is very interesting, but I believe it is more suitable for a communication with a discussion format, rather than question answering, so that after a while a community consensus is formed, rather than electing an answer as best , which can be far from optimal.  
> **username_1**: The community decision seems to be to keep the question open. It'll be good to get some fresh young minds looking at the problem.  
> **username_4**: but it should really be CW.  
> **username_5**: What is the motivation of this question?  And what do you mean by “explaining the P=NP problem”?  For example, if you somehow have to explain the _precise formulation_ of the P=NP problem so that a ten-year-old child can understand it, then you are almost surely out of luck.  
> **username_0**: If a thing cannot be explained in five minutes, either it is not well understoodd it or it doesn't work. The culture of stackoverflow sites have been to allow dumb questions as well and there is no mention that this is a site only for the research level. Research level wont resort to QA sites I'm sure of that. Science of one century is the common sense of the next. If this site stands for hundred years, may be we have the earliest layman explanation of the problem?  
> **username_5**: 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.  
> **username_6**: This is a cool question.  I hope that the great answers are recognized as they are added over time.  
> **username_7**: see also [everyday encounters with NP complete problems](http://cstheory.stackexchange.com/questions/446/everyday-encounters-with-np-complete-problems)  

---

## 8 answers

### Answer by username_8 on 2011-02-28. Score: 37

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](https://i.sstatic.net/MeDkj.png)
![Bin packing is NP complete 1](https://i.sstatic.net/eNbe7.png)
![Bin packing is NP complete 2](https://i.sstatic.net/Bhtsx.png)

> **Comments:**
> **username_10**: Very easy to understand.  
> **username_11**: I think "no easy way" need to be expanded on including scaling as the number of blocks gets bigger  
> **username_12**: Very nice example but isn't it called the Rectangle Packing problem in the literature?  
> **username_9**: Necropost, and call me horribly stupid and retarded, but how is this problem in NP? How can you verify that a given packing is the optimal packing in polynomial time?  
> **username_8**: @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)).  
> **username_9**: Oh, so the decision problem is "is there a feasible solution". I see.  

---

### Answer by username_13 on 2011-02-27. Score: 22

In this talk [Scott Aaronson](https://cstheory.stackexchange.com/users/1575/scott-aaronson) addresses the question.

**[TEDxCaltech - Scott Aaronson - Physics in the 21st Century: Toiling in Feynman's Shadow](http://www.youtube.com/watch?v=SczraSQE3MY)**

**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**](http://en.wikipedia.org/wiki/Eight_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}$.

> **Comments:**
> **username_1**: Perhaps you could summarise the essence of Scott's explanation.  
> **username_14**: I've always been curious what all the P=NP fuss is about, now I do!  
> **username_15**: Since P ∈ NP, maybe clarify that you are talking about the non-P part of NP here.  
> **username_16**: +1 Many great answers in this thread, but this is the only one that even attempts to define what P and NP even mean!  
> **username_13**: @BROY If I could answer that I would be millionaire and win Turing award or two!  

---

### Answer by username_17 on 2011-02-28. Score: 19

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.

> **Comments:**
> **username_18**: Good one. It probably does not matter that factoring is incidentally a bad example (or is it?).  
> **username_17**: 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.....  
> **username_19**: Subset sum problem can be explained to pupils who didn't study multiplication yet!  

---

### Answer by username_2 on 2011-02-27. Score: 8

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.


---

### Answer by username_20 on 2012-03-01. Score: 5

Michael Sipser explains the P vs NP problem in a highly intuitive way in [this video](http://www.youtube.com/watch?v=msp2y_Y5MLE).


---

### Answer by username_21 on 2011-02-28. Score: 2

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.

> **Comments:**
> **username_1**: This is not an answer to the question.  
> **username_21**: 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?  
> **username_5**: 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.  
> **username_22**: 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  
> **username_22**: [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.  
> **username_5**: I may agree with this answer, depending on what the asker meant by “explain the P=NP problem.”  I realized that the question was very vague.  

---

### Answer by username_7 on 2012-01-27. Score: 0

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](http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf) Merlijn Sevenster ICGA journal sep 2004

[minesweeper is NP complete FAQ](http://web.mat.bham.ac.uk/R.W.Kaye/minesw/FAQ.htm) 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!](http://arxiv.org/abs/1201.4995) 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](http://www.extremetech.com/gaming/115677-pac-man-is-np-hard-same-as-travelling-salesman-problem) extreme tech mag article on above paper

> **Comments:**
> **username_7**: see also [A SURVEY OF NP-COMPLETE PUZZLES](http://red.cs.nott.ac.uk/~gxk/papers/icga2008_preprint.pdf) by Kendall, Parkes, Spoerer, and [Playing games with algorithms: Algorithmic Combinatorial Game Theory](http://arxiv.org/abs/cs.CC/0106019) by Demaine and Hearn  

---

### Answer by username_0 on 2011-03-01. Score: 0

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.

> **Comments:**
> **username_24**: It might be worth tightening the text.  Have you tried reading this aloud?  
> **username_0**: Everything should't be tightened like mathematical definitions I think.  
> **username_11**: 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.  
> **username_23**: 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: http://mathoverflow.net/questions/27944/do-there-exist-chess-positions-that-require-exponentially-many-moves-to-reach.  
> **username_23**: This link is maybe more clear than the previous: http://cstheory.stackexchange.com/questions/6563/what-is-the-computational-complexity-of-solving-chess  

---

