Answers.Body: <p>First, note the difference between <a href="https://en.wikipedia.org/wiki/NP_(complexity)" rel="nofollow noreferrer">NP</a> and <a href="https://en.wikipedia.org/wiki/NP-hardness" rel="nofollow noreferrer">NP-hard</a>. NP simply means verifiable easily. NP-hard means verifiable easily, but also means that the problem is as hard to solve as the hardest problems in NP, which are not known to be easily solvable (see <a href="https://en.wikipedia.org/wiki/P_versus_NP_problem" rel="nofollow noreferrer">P = NP</a>).</p>
  
  <p>For describing what it means for a problem to be NP-hard, I have had success by referring to the canonical <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow noreferrer">Traveling Salesman Problem</a>. I might introduce the problem like this:</p>
  
  <p>Given a list of cities, the distances between each pair of cities, and a number $k$, is there a path of length ≤ $k$ that visits each city and returns to the start city?</p>
  
  <p>And then I would say something like:</p>
  
  <p>If someone tells you a path to take i.e. an ordered list of cities, you can quite easily check to see if it includes every city, starts and ends at the same city, and is of length ≤ $k$. However, trying to come up with that path in the first place is more difficult. You could imagine trying every possibility exhaustively, checking if the conditions hold for each one. While there are algorithms better than this brute-force approach, which has runtime that is exponential in the number of cities, none have been shown to be polynomial in the number of cities.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-30T17:00:44.370Z
Answers.LastActivityDate: 2018-04-30T17:39:46.500Z
Answers.LastEditDate: 2018-04-30T17:39:46.500Z
Answers.UserDisplayName: Samasambo
Answers.Body: <p>Map coloring is a very nice example.</p>
  
  <p>It is NP to find if the graph is planar or not (you can reduce the map coloring if a graph is planar or not), but it is relatively easy to see if the colored map has &lt;= 4 colors.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-16T15:21:13.633Z
Answers.Text: That's a much more intuitive example. Thanks!
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-29T02:01:52.880Z
Answers.Text: I'm not sure what this example is supposed to show, but actually [planarity can be tested in linear time](http://www.combinatorialmath.ca/g&g/articles/planarity.pdf), whereas testing whether a graph is 4-colorable is NP-complete.
Answers.UserDisplayName: Yuval Filmus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-04T20:30:05.497Z
Answers.Text: @YuvalFilmus The four color theorem was proved in 1976. It was the first major theorem to be proved using a computer. If a graph can be shown to be planar in linear time, then it must also be 4-colorable, no?
Answers.UserDisplayName: Draco18s no longer trusts SE
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-04T20:32:04.217Z
Answers.Text: @Draco18s Hint: $K_{3,3}$ is 2-colorable although it's not planar.
Answers.UserDisplayName: Yuval Filmus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-04T20:37:21.690Z
Answers.Text: @YuvalFilmus Ah, I was thinking about it backwards. :)
Answers.UserDisplayName: Draco18s no longer trusts SE
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-16T14:52:45.273Z
Answers.LastActivityDate: 2017-06-16T14:52:45.273Z
Answers.UserDisplayName: MTSan
Answers.Body: <p>Start with the humor of <a href="https://xkcd.com/287/" rel="noreferrer">xkcd</a>:
  <a href="https://i.sstatic.net/00Ciy.png" rel="noreferrer"><img src="https://i.sstatic.net/00Ciy.png" alt="XKCD comic #287 on NP-complete problems"></a></p>
  
  <p>I used the above comic in a lecture on P vs. NP. The analogy I gave is eating at The Cheesecake Factory. Their <a href="https://www.thecheesecakefactory.com/menu/" rel="noreferrer">menu</a> boasts something like 250 dishes and 50 kinds of cheesecake. It's a tome to wade through.</p>
  
  <p>Now, imagine a scenario like this: You are given a $50 gift card to The Cheesecake Factory. You can order anything you want. Let's say for fun that you will limit your indulgence to 1500 calories. What is the most food you can order while staying under that limit? Good luck.</p>
  
  <p>The struggle of ordering food at a restaurant with a menu like this while also obeying constraints of money and calories while maximizing enjoyment and possibly quantity gets at the essence of the <a href="https://en.wikipedia.org/wiki/Knapsack_problem" rel="noreferrer">knapsack problem</a> (Can a value of at least V be achieved without exceeding the weight W?). While it's an analogy, I think it does help to illustrate the nature of the problem. (Tangent: my wife and I went here to eat shortly after this lecture, and I tried to explain that my taking so long to decide was due to the fact that it was an NP-complete problem.)</p>
  
  <p>I also think trying to schedule a meeting with a handful of people can also be a helpful analogy for the Boolean satisfiability problem. I found <a href="http://sat.inesc-id.pt/~ines/sac10.pdf" rel="noreferrer">these lecture slides</a> in my research on examples to use in class. Slide 3 provides a practical example where four people try to find a day on which they can meet. Imagine you have a committee of 10+ people with all sorts of constraints. This is absolutely a real-world example of something that is a) difficult for humans to unpack algorithmically beyond brute force and b) easy to verify once it works for everyone. As the first known NP-complete problem, it's a great place to begin this conversation.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-19T18:31:20.827Z
Answers.LastActivityDate: 2018-04-19T18:31:20.827Z
Answers.UserDisplayName: Peter
Answers.Body: <p>The <a href="https://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow noreferrer">subset sum problem</a> is one that is easy to understand - "given this set of numbers {provide a set of a dozen or so}, is there a subset of these numbers that sum up to 100?"</p>
  
  <p>For example, the set <code>49, 55, 79, 67, 47, 12, 60, 84, 52, 44, 43, 47, 93, 68, 70, 96, 19, 22, 62, 79</code>.  Theres only one solution for the sum to 100:</p>
  
  <ul>
  <li>12 19 22 47</li>
  </ul>
  
  <p>Determining this will take non-deterministic polynomial time. Trivially just guess the answer. </p>
  
  <p>However, determining the answer "yes, this set sums to 100" can be determined in linear time.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-24T00:27:45.560Z
Answers.LastActivityDate: 2018-04-27T12:50:38.077Z
Answers.LastEditDate: 2018-04-27T12:50:38.077Z
Answers.UserDisplayName: user4934
Answers.Body: <p>If your student has tried it once, you can use sudoku as an example (it does not work so well if the student has never heard of it). </p>
  
  <ul>
  <li><p>Given a completed sudoku grid, write a program that verifies that it is valid: your student can probably write this simple program in a few minutes, or if you give the answer see that it is really easy.</p></li>
  <li><p>Given an incomplete sudoku grid, write a program that completes it. Much harder (although semi-naive backtracking works well for 9x9 grids)!</p></li>
  </ul>
  
  <p>It gets even better because, if you already gave the Map coloring (or graph coloring example), you can show easily that a 9x9 sudoku is just a particular instance of graph coloring and this becomes a good example for NP-<em>completeness</em>. (Just remark that a 9x9 sudoku is just a graph where each vertex corresponds to a cell in the sudoku, and an edge between two vertices means that the two corresponding cells are in the same row, column or block. Once a graph is built, try to 9-color it).</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-17T13:48:52.027Z
Answers.Text: I never realized that sudoku-solving is an NP problem. I've assigned this as a (hard) lab before - I will do so again prior to the NP unit. And with the way it links to MT San's example... what a cool setup!
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-17T06:42:52.477Z
Answers.LastActivityDate: 2017-06-17T06:42:52.477Z
Answers.UserDisplayName: Kim Nguyễn
Answers.Body: <p>Complexity class <code>NP</code>_ is described here: <a href="https://en.wikipedia.org/wiki/NP_(complexity)" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/NP_(complexity)</a>.</p>
  
  <p>One of the easiest examples to explain is given there as: The decision problem version of the <em>integer factorization problem</em>: given  integers n and k, is there a factor f with 1 &lt; f &lt; k and f dividing n?</p>
  
  <p>It is easy to explain as most students will understand factorization and will know, or can be convinced, that finding factors is a hard problem. It is also clear that a solution (factor), once found/guessed, is easily checked. </p>
  
  <p>Showing that it is in class NP is a harder slog, of course. </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-19T21:29:52.190Z
Answers.Text: Why is it hard to show that factoring is in NP? Long multiplication is clearly in P, and that's the most expensive part if the certificate consists of both factors.
Answers.UserDisplayName: Peter Taylor
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-19T21:35:53.090Z
Answers.Text: It just requires an argument whereas the other parts are almost obvious. It also is complicated by the dual definitions of NP.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-19T18:47:35.637Z
Answers.LastActivityDate: 2018-04-19T20:42:19.893Z
Answers.LastEditDate: 2018-04-19T20:42:19.893Z
Answers.UserDisplayName: Buffy
Answers.Body: <p>Please note that all P problems are in NP too, since they are easy to solve and therefore also easy to verify. </p>
  
  <p>Maybe you are asking for an NP-complete problem. In that case I think the sudoku mentioned above is a good example if the student is familiar with that</p>
  
  <p>In a different case, the <a href="https://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow noreferrer">subset sum</a> problem is my second option.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-18T15:37:59.210Z
Answers.LastActivityDate: 2018-04-18T15:37:59.210Z
Answers.UserDisplayName: Panagiotis Grontas
Body: <p>I was talking to a student today, and explaining that NP problems are hard to solve, but easy to verify.  I used password encryption/decryption as an example, but he got stuck.  He was unable to fathom how, given the hash, you couldn't just reverse your steps backwards to the password.</p>
  
  <p>I started explaining a bit about encryption, but I came to think that my example was fundamentally not a very good one.  My goal is not to get into the weeds with encryption, my goal is to be able to explain what an NP problem is in a really intuitive way.</p>
  
  <p>What is a clear analogy or example to describe NP?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-16T16:08:20.887Z
Comments.Text: I can not remember the complexity, but busy beaver is easy to understand, easy to prove a given solution, and really really really hard to solve for more than 4 or 5 nodes. For 1 and 2 nodes it is trivial, for around 3 it get to be an hours lesson. By 5 no one has done it yet.
Comments.UserDisplayName: ctrl-alt-delor
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-18T23:50:57.610Z
Comments.Text: Knapsack problem: https://imgs.xkcd.com/comics/np_complete.png
Comments.UserDisplayName: Ellen Spertus
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-19T21:33:52.983Z
Comments.Text: "*NP problems are hard to solve*" is not true, which makes it unclear whether the actual question is about NP, NP-hard, or something else.
Comments.UserDisplayName: Peter Taylor
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-27T13:32:31.467Z
Comments.Text: A simplified example of why hashing is one-way: the modulus operator (it's also one-way). There are multiple (infinite) inputs that give the same output. Given `x % 10 == 3`, what is `x`? It could be any number ending in `3`.
Comments.UserDisplayName: mbomb007
Tags: <teaching-analogy><complexity-theory>
Title: Intuitive example of an NP problem
ThreadText: # Intuitive example of an NP problem
  
  (Asked by: username_0 on 2017-06-16)
  
  I was talking to a student today, and explaining that NP problems are hard to solve, but easy to verify. I used password encryption/decryption as an example, but he got stuck. He was unable to fathom how, given the hash, you couldn't just reverse your steps backwards to the password.
  
  I started explaining a bit about encryption, but I came to think that my example was fundamentally not a very good one. My goal is not to get into the weeds with encryption, my goal is to be able to explain what an NP problem is in a really intuitive way.
  
  What is a clear analogy or example to describe NP?
  
  **Tags:** teaching-analogy, complexity-theory
  
  > **Comments:**
  > **username_1**: I can not remember the complexity, but busy beaver is easy to understand, easy to prove a given solution, and really really really hard to solve for more than 4 or 5 nodes. For 1 and 2 nodes it is trivial, for around 3 it get to be an hours lesson. By 5 no one has done it yet.  
  > **username_2**: Knapsack problem: https://imgs.xkcd.com/comics/np_complete.png  
  > **username_3**: "*NP problems are hard to solve*" is not true, which makes it unclear whether the actual question is about NP, NP-hard, or something else.  
  > **username_4**: A simplified example of why hashing is one-way: the modulus operator (it's also one-way). There are multiple (infinite) inputs that give the same output. Given `x % 10 == 3`, what is `x`? It could be any number ending in `3`.  
  
  ---
  
  ## 7 answers
  
  ### Answer by username_11 on 2017-06-17. Score: 8
  
  If your student has tried it once, you can use sudoku as an example (it does not work so well if the student has never heard of it).
  
  * Given a completed sudoku grid, write a program that verifies that it is valid: your student can probably write this simple program in a few minutes, or if you give the answer see that it is really easy.
  * Given an incomplete sudoku grid, write a program that completes it. Much harder (although semi-naive backtracking works well for 9x9 grids)!
  
  It gets even better because, if you already gave the Map coloring (or graph coloring example), you can show easily that a 9x9 sudoku is just a particular instance of graph coloring and this becomes a good example for NP-*completeness*. (Just remark that a 9x9 sudoku is just a graph where each vertex corresponds to a cell in the sudoku, and an edge between two vertices means that the two corresponding cells are in the same row, column or block. Once a graph is built, try to 9-color it).
  
  > **Comments:**
  > **username_0**: I never realized that sudoku-solving is an NP problem. I've assigned this as a (hard) lab before - I will do so again prior to the NP unit. And with the way it links to MT San's example... what a cool setup!  
  
  ---
  
  ### Answer by username_6 on 2017-06-16. Score: 6
  
  Map coloring is a very nice example.
  
  It is NP to find if the graph is planar or not (you can reduce the map coloring if a graph is planar or not), but it is relatively easy to see if the colored map has <= 4 colors.
  
  > **Comments:**
  > **username_0**: That's a much more intuitive example. Thanks!  
  > **username_7**: I'm not sure what this example is supposed to show, but actually [planarity can be tested in linear time](http://www.combinatorialmath.ca/g&g/articles/planarity.pdf), whereas testing whether a graph is 4-colorable is NP-complete.  
  > **username_8**: @username_7 The four color theorem was proved in 1976. It was the first major theorem to be proved using a computer. If a graph can be shown to be planar in linear time, then it must also be 4-colorable, no?  
  > **username_7**: @username_8 Hint: $K_{3,3}$ is 2-colorable although it's not planar.  
  > **username_8**: @username_7 Ah, I was thinking about it backwards. :)  
  
  ---
  
  ### Answer by username_9 on 2018-04-19. Score: 5
  
  Start with the humor of [xkcd](https://xkcd.com/287/):
  [![XKCD comic #287 on NP-complete problems](https://i.sstatic.net/00Ciy.png)](https://i.sstatic.net/00Ciy.png)
  
  I used the above comic in a lecture on P vs. NP. The analogy I gave is eating at The Cheesecake Factory. Their [menu](https://www.thecheesecakefactory.com/menu/) boasts something like 250 dishes and 50 kinds of cheesecake. It's a tome to wade through.
  
  Now, imagine a scenario like this: You are given a $50 gift card to The Cheesecake Factory. You can order anything you want. Let's say for fun that you will limit your indulgence to 1500 calories. What is the most food you can order while staying under that limit? Good luck.
  
  The struggle of ordering food at a restaurant with a menu like this while also obeying constraints of money and calories while maximizing enjoyment and possibly quantity gets at the essence of the [knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem) (Can a value of at least V be achieved without exceeding the weight W?). While it's an analogy, I think it does help to illustrate the nature of the problem. (Tangent: my wife and I went here to eat shortly after this lecture, and I tried to explain that my taking so long to decide was due to the fact that it was an NP-complete problem.)
  
  I also think trying to schedule a meeting with a handful of people can also be a helpful analogy for the Boolean satisfiability problem. I found [these lecture slides](http://sat.inesc-id.pt/~ines/sac10.pdf) in my research on examples to use in class. Slide 3 provides a practical example where four people try to find a day on which they can meet. Imagine you have a committee of 10+ people with all sorts of constraints. This is absolutely a real-world example of something that is a) difficult for humans to unpack algorithmically beyond brute force and b) easy to verify once it works for everyone. As the first known NP-complete problem, it's a great place to begin this conversation.
  
  
  ---
  
  ### Answer by username_10 on 2018-04-24. Score: 5
  
  The [subset sum problem](https://en.wikipedia.org/wiki/Subset_sum_problem) is one that is easy to understand - "given this set of numbers {provide a set of a dozen or so}, is there a subset of these numbers that sum up to 100?"
  
  For example, the set `49, 55, 79, 67, 47, 12, 60, 84, 52, 44, 43, 47, 93, 68, 70, 96, 19, 22, 62, 79`. Theres only one solution for the sum to 100:
  
  * 12 19 22 47
  
  Determining this will take non-deterministic polynomial time. Trivially just guess the answer.
  
  However, determining the answer "yes, this set sums to 100" can be determined in linear time.
  
  
  ---
  
  ### Answer by username_12 on 2018-04-19. Score: 2
  
  Complexity class `NP`\_ is described here: <https://en.wikipedia.org/wiki/NP_(complexity)>.
  
  One of the easiest examples to explain is given there as: The decision problem version of the *integer factorization problem*: given integers n and k, is there a factor f with 1 < f < k and f dividing n?
  
  It is easy to explain as most students will understand factorization and will know, or can be convinced, that finding factors is a hard problem. It is also clear that a solution (factor), once found/guessed, is easily checked.
  
  Showing that it is in class NP is a harder slog, of course.
  
  > **Comments:**
  > **username_3**: Why is it hard to show that factoring is in NP? Long multiplication is clearly in P, and that's the most expensive part if the certificate consists of both factors.  
  > **username_12**: It just requires an argument whereas the other parts are almost obvious. It also is complicated by the dual definitions of NP.  
  
  ---
  
  ### Answer by username_13 on 2018-04-18. Score: 2
  
  Please note that all P problems are in NP too, since they are easy to solve and therefore also easy to verify.
  
  Maybe you are asking for an NP-complete problem. In that case I think the sudoku mentioned above is a good example if the student is familiar with that
  
  In a different case, the [subset sum](https://en.wikipedia.org/wiki/Subset_sum_problem) problem is my second option.
  
  
  ---
  
  ### Answer by username_5 on 2018-04-30. Score: 1
  
  First, note the difference between [NP](https://en.wikipedia.org/wiki/NP_(complexity)) and [NP-hard](https://en.wikipedia.org/wiki/NP-hardness). NP simply means verifiable easily. NP-hard means verifiable easily, but also means that the problem is as hard to solve as the hardest problems in NP, which are not known to be easily solvable (see [P = NP](https://en.wikipedia.org/wiki/P_versus_NP_problem)).
  
  For describing what it means for a problem to be NP-hard, I have had success by referring to the canonical [Traveling Salesman Problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem). I might introduce the problem like this:
  
  Given a list of cities, the distances between each pair of cities, and a number $k$, is there a path of length ≤ $k$ that visits each city and returns to the start city?
  
  And then I would say something like:
  
  If someone tells you a path to take i.e. an ordered list of cities, you can quite easily check to see if it includes every city, starts and ends at the same city, and is of length ≤ $k$. However, trying to come up with that path in the first place is more difficult. You could imagine trying every possibility exhaustively, checking if the conditions hold for each one. While there are algorithms better than this brute-force approach, which has runtime that is exponential in the number of cities, none have been shown to be polynomial in the number of cities.
  
  
  ---
  
  