11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ctrl-alt-delor Jun 16 '17 at 16:08
  • $\begingroup$ If x=3 and y=5 then x+y=8. Given 17, what are x and y? The student might be able to grasp the Knapsack problem, with a clear explanation. $\endgroup$ – user737 Jun 17 '17 at 16:01
  • $\begingroup$ Knapsack problem: imgs.xkcd.com/comics/np_complete.png $\endgroup$ – Ellen Spertus Apr 18 '18 at 23:50
  • 1
    $\begingroup$ "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. $\endgroup$ – Peter Taylor Apr 19 '18 at 21:33
  • $\begingroup$ 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. $\endgroup$ – mbomb007 Apr 27 '18 at 13:32
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's a much more intuitive example. Thanks! $\endgroup$ – Ben I. Jun 16 '17 at 15:21
  • 2
    $\begingroup$ I'm not sure what this example is supposed to show, but actually planarity can be tested in linear time, whereas testing whether a graph is 4-colorable is NP-complete. $\endgroup$ – Yuval Filmus Jun 29 '17 at 2:01
  • $\begingroup$ @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? $\endgroup$ – Draco18s May 4 '18 at 20:30
  • 1
    $\begingroup$ @Draco18s Hint: $K_{3,3}$ is 2-colorable although it's not planar. $\endgroup$ – Yuval Filmus May 4 '18 at 20:32
  • $\begingroup$ @YuvalFilmus Ah, I was thinking about it backwards. :) $\endgroup$ – Draco18s May 4 '18 at 20:37
8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – Ben I. Jun 17 '17 at 13:48
  • 1
    $\begingroup$ I am not a sudoku fan, but relating it to map coloring is absolutely stunning! "This is a good day to die!" $\endgroup$ – user737 Jun 17 '17 at 16:05
2
$\begingroup$

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 problem is my second option.

$\endgroup$
4
$\begingroup$

Start with the humor of xkcd: XKCD comic #287 on NP-complete problems

I used the above comic in a lecture on P vs. NP. The analogy I gave is eating at The Cheesecake Factory. Their 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 (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 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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Taylor Apr 19 '18 at 21:29
  • $\begingroup$ It just requires an argument whereas the other parts are almost obvious. It also is complicated by the dual definitions of NP. $\endgroup$ – Buffy Apr 19 '18 at 21:35
4
$\begingroup$

The 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.

$\endgroup$
1
$\begingroup$

First, note the difference between NP and NP-hard. 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).

For describing what it means for a problem to be NP-hard, I have had success by referring to the canonical Traveling 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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