Intuitive example of an NP problem

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

Start with the humor of xkcd:

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.