<p>Some "every day" problems that are NP-hard, appropriately formulated:</p>

<ul>
<li><p>Assigning university classes to timeslots to minimize scheduling conflicts.</p></li>
<li><p>Assigning wedding guests to seats so that friends sit at the same table, but enemies do not.</p></li>
<li><p>Planning a road trip to visit all of the tourist spots on a list, so as to minimize driving.</p></li>
</ul>

CC BY-SA 2.5
2010-08-24T15:52:19.600Z
2010-08-24T15:52:19.600Z
Aaron Roth
<p>My favorite example to use with non-CS friends is this one:</p>

<p><a href="http://www.cs.cmu.edu/~sandholm/kidneyExchange.EC07.withGrantInfo.pdf">Abraham, A. Blum, Sandholm.  Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges.  EC07.</a></p>

<p>Kidney exchange markets are essentially a restricted form of cycle cover.  I like this example because a) it's easy to explain the gist(if you leave out some of the more technical details) and b) it's one of the few instances I know of where better algorithms can literally save lives!</p>

<p>My second favorite example is the hospitals-and-residents problem (aka the college admissions problem).  Each hospital ranks all residents (graduating medical students) and residents rank hospitals.  Each hospital has a certain number of slots.  From there it's a stable matching problem and can be solved in polynomial time.</p>

<p>But in reality, couples can enter the system (yes, there is indeed <a href="http://en.wikipedia.org/wiki/National_Resident_Matching_Program">a system</a>) together, so that the system won't, for example, split up married couples who are both applying for residency.  The addition of couples makes the problem NP-complete.  In addition to being easy to explain, this nicely demonstrates how the introduction of long-range connections can induce NP-completeness.</p>

CC BY-SA 2.5
2010-08-24T16:38:59.070Z
Great example!

David Manlove has worked extensively on these kinds of problems (both exchange and matching); the systems are being used in the UK and Hungary.  http://www.dcs.gla.ac.uk/~davidm/publications.html

As far as I know, these approaches beat the NRMP algorithms, and Eric McDermid's 3/2-approximation algorithm is the best known.  http://dx.doi.org/10.1007/978-3-642-02927-1_57
András Salamon
CC BY-SA 2.5
2010-08-24T14:53:28.957Z
2010-08-24T14:53:28.957Z
Joshua Grochow
<p>The traveling salesman problem is apparently accessible... at least where I am, this seems to be the most popular CS problem among non-CS folks by far. I also found the following illustration of Vertex Cover quite appealing, as introduced by my algorithms instructor: </p>

<p>You have a road network and wish to ensure that if a car is stuck out of fuel, there is a gas station on at least one end of the road. </p>

<p>As a city planner, you want to minimize costs by building the fewest number of gas stations possible. This is essentially the vertex cover problem, and I have found some success in pointing out that although you don't expect to find the optimal vertex cover in polynomial time, you can find something that is only a factor of two away in polynomial time, by simply picking up both endpoints of a maximum matching (well, that last detail might be omitted depending on how keen your audience is - especially since the MM algorithm isn't exactly a two-liner). </p>

<p>As for an example of a 'jump in complexity' with a small change in the nature of the problem, I think the difference between checking 2-colorability and 3-colorability makes a good example. With all the publicity surrounding the four-color theorem, one might also point out that checking whether a map can be properly colored with only three colors instead of four is hard, even though we know that it can always be colored with four colors. A fair number of people find this quite startling. </p>

<p>Another fairly natural situation is the <a href="http://en.wikipedia.org/wiki/Feedback_vertex_set#Applications">deadlock recovery problem</a> in operating systems. This is modeled by the NP-complete problem of feedback vertex set - the smallest number of vertices whose removal makes the graph acyclic - and I find this to be a remarkable example as well (and is explained further in that wikipedia article).</p>

CC BY-SA 2.5
2010-10-05T23:46:19.153Z
A *maximal* matching is enough for a two-approximation, which is much easier to compute and explain.
Warren Schudy
CC BY-SA 2.5
2010-10-16T08:12:27.630Z
@Warren: Thank you for pointing that out, of course you're quite right!
Neeldhara
CC BY-SA 2.5
2010-08-29T14:44:59.110Z
2010-08-29T14:44:59.110Z
Neeldhara
<p>I think parallel parking is NP-hard.</p>

<p>In fact, the more general problem of finding the shortest path with bounded curvature that takes a polygonal object from its initial position to its final position in a polygonal environment is NP-hard. The proof can be found here - <a href="http://portal.acm.org/citation.cfm?id=298976">http://portal.acm.org/citation.cfm?id=298976</a></p>

CC BY-SA 4.0
2019-12-09T17:50:21.563Z
Much much belated: the latter is a great example (though 'hard' != 'complete' of course, and I think the 'benchmark' for almost all motion planning problems is PSPACE), but now I'm curious — is the problem still formally hard if the object is convex, or even a box?
Steven Stadnicki
CC BY-SA 2.5
2010-08-31T22:18:20.227Z
2010-08-31T22:18:20.227Z
Vinayak Pathak
<p>Knapsack is pretty easy to grasp, especially for anyone who has had to deal with a small suitcase.. a nice example if they know dynamic programming.</p>

<p>Another fun (practically identical) one is Subset-sum, because it also has a nice physical interpretation: imagine the numbers being the distances of equal point-masses on an ideal (massless) ruler, with the fulcrum at the origin.  Subset-sum says: does there exist a non-empty subset such that the ruler will remain balanced?  (i.e., such that the center of gravity is the support point for the ruler?)</p>

<p>In both cases, it seems intuitive that naive strategies may force resorting to checking all subsets.</p>

<p>If they have more background, it's nice to grow problems by dropping constraints.  For example, starting with a max flow problem, turning it into a linear program, and making it an integer program.  (A great one of course is MAX-CUT, since to people with more background you can also bring up UGC; I touch some of this in an MO answer <a href="https://mathoverflow.net/questions/33036/is-quadratic-programming-still-np-hard-if-you-have-bounds-and-a-feasible-point/33048#33048">https://mathoverflow.net/questions/33036/is-quadratic-programming-still-np-hard-if-you-have-bounds-and-a-feasible-point/33048#33048</a> .) Also there are neat things like problems seemingly similar which have vastly different complexity (Euler (edge) path is linear time, Hamiltonian (vertex) path is NP-complete).</p>

CC BY-SA 4.0
2020-07-03T18:02:02.503Z
Or just this brilliant xkcd strip: https://xkcd.com/287/
delete000
CC BY-SA 2.5
2010-08-24T17:06:51.897Z
I like the following version of Subset Sum: you are given £10 to buy snacks from a shop.  Can you find exactly the right combination of purchases so that no money is left over?
András Salamon
CC BY-SA 2.5
2010-08-23T23:19:26.147Z
2010-08-23T23:19:26.147Z
2017-04-13T12:57:54.777Z
matus
<p>Crossword puzzle construction is NP-Complete: Given a set of answers, try to fit them into a grid.</p>

CC BY-SA 2.5
2010-08-24T16:12:38.647Z
2010-08-24T16:12:38.647Z
Aryabhata
<p>I created the website Tagxedo, <a href="http://www.tagxedo.com" rel="noreferrer">http://www.tagxedo.com</a>, a word cloud generator that fits words (sized by their frequencies) into shape.  The results are very pretty, but the problem is easily proven to be NP-hard (packing problem).</p>

<p>Interestingly, many NP-hard problems have "easy" approximations.  Tagxedo seems to be doing an almost perfect job in many cases.  This leads to interesting discussion about the practical implication of P vs NP, and the topic of approximation.</p>

CC BY-SA 2.5
2010-09-01T04:33:54.897Z
2010-09-01T04:33:54.897Z
Hardy Leung
<p><a href="https://journals.aps.org/prx/abstract/10.1103/PhysRevX.7.041070" rel="noreferrer">Refolding an unfolded origami</a> is NP-hard.</p>

CC BY-SA 4.0
2019-12-05T22:52:03.840Z
2019-12-05T22:52:03.840Z
delete000
<p>One of my friends spent a sabbatical year watching a baseball game in every major league stadium in North America.  Without flying.  (He didn't <em>quite</em> succeed; three stadiums were under construction that year.)</p>

CC BY-SA 2.5
2010-08-26T04:27:51.790Z
yes, but was he trying to minimize his gas usage ? :)
Suresh Venkat
CC BY-SA 2.5
2010-08-26T05:32:20.153Z
Even finding a feasible schedule was NP-hard, because stadiums are not open every day (Hamiltonian cycle with time windows).
Jeffε
CC BY-SA 2.5
2010-08-25T21:47:23.923Z
2010-08-25T21:47:23.923Z
Jeffε
<p>Due to the success of companies like Uber and Lyft, many people have a very accessible direct experience with NP-complete problems.</p>

<blockquote>
  <p>Given a collection of drivers and a list of people who want to be picked up at various times, what is the most efficient allocation of passengers to drivers?</p>
</blockquote>

<p>This problem (when suitably rephrased) is NPC and I imagine that people have at some point wondered how Uber decides to pair drivers and passengers.</p>

CC BY-SA 3.0
2017-10-25T18:23:06.690Z
2017-10-27T14:04:43.243Z
2017-10-27T14:04:43.243Z
Stella Biderman
<p>An Np-complete problem like Sudoku (on nxn sqaure) is like a Universal tool which enables us to efficiently solve all problems that have efficiently verifiable solutions. The only requirement is to have an efficient method to solve Sudoku.</p>

CC BY-SA 2.5
2010-08-25T13:48:37.000Z
2010-08-25T13:48:37.000Z
Mohammad Al-Turkistany
<p>I usually use SAT as an example. I say something like "all sorts of problems that come up all the time can be rewritten as looking for a true assignment to a big logic formula. The P vs NP question is whether is there a fundamentally easier way to solve this logic formula than just trying all possibilities. So far no one has been able to either find a way or prove that there is no easy way out".</p>

CC BY-SA 2.5
2010-09-01T08:04:29.407Z
I'm not sure how many people encounter this every day.
Dave Clarke
CC BY-SA 2.5
2010-08-23T22:59:34.680Z
2010-08-23T22:59:34.680Z
Alexandre Passos
<p>A whimsically accessible example is a <a href="https://perl.plover.com/yak/Elmo/" rel="nofollow noreferrer">brief presentation</a> by Mark Dominus (see the <a href="https://blog.plover.com/CS/elmo.html" rel="nofollow noreferrer">related blog post</a>) called “My Favorite NP-Complete Problem” where the image below is the punchline of an overview of <a href="https://en.wikipedia.org/wiki/Exact_cover" rel="nofollow noreferrer">exact cover by 3-sets</a>.</p>

<p>Titles in the video series include</p>

<ul>
<li><em>Dancing, Music, &amp; Books</em></li>
<li><em>Hands, Ears, &amp; Feet</em></li>
<li><em>Wake Up with Elmo</em> (about sleeping, getting dressed, and brushing your teeth)</li>
<li><em>People in Your Neighborhood</em> (about firefighters, lifeguards, and nurses)</li>
</ul>

<p>The clear intent was for each video to contain three episodes all on a common theme drawn from a pool of topics of interest to young children.</p>

<p>The odd duck in the series was a video on “flowers, bananas, and … hair.”</p>

<p><a href="https://i.sstatic.net/0vvkt.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/0vvkt.jpg" alt="Flowers, bananas, and … hair."></a></p>

CC BY-SA 3.0
2017-10-25T17:45:06.910Z
2017-10-25T17:45:06.910Z
Greg Bacon
<p>Scheduling is around us on an almost daily basis.  Whether it be the workplace, manufacturing, or just planning your day, you'll find an $NP$-complete problem that you wish had an efficient exact algorithm.  A situation that arises commonly in scheduling is parallel machine scheduling (typically non-preemptive, and tasks occur in parallel). A trivial way of visualizing parallel machine scheduling problems is stacking blocks.</p>

<p>For instance, finding an assignment of $n$ blocks of varying heights (say $p_j$) with $m$ towers (blocks are stacked to form) with the goal of minimizing the height of the tallest tower is $NP$-hard.  This is equivalent to the makespan problem on identical parallel machines (replace tasks/jobs of length $p_j$ for blocks, towers for machines, and tallest height for the <em>completion time of the machine that finishes last</em> (called the makespan)).  Asking if there is a tower of height at most $k$ would then be $NP$-complete in this situation.  Observe that this doesn't need to be blocks providing we assume they can't topple over.  It could be stacks of papers, crates, or plates.</p>

<p>Hope this helps! </p>

CC BY-SA 3.0
2015-01-27T03:11:27.293Z
2015-01-27T03:11:27.293Z
PageWizard
<p>I like to introduce Vertex-Cover as a problem in which the underlying graph models a museum, so that the vertices represent the museum rooms and the edges represent the corridors. Then, it is easy for the students to understand that minimising the number of guards required to watch over the museum corresponds to finding a vertex cover. The guards are placed at the doors of the selected rooms (vertices) and cover the corresponding corridors (edges). </p>

CC BY-SA 4.0
2019-12-10T16:51:49.497Z
This reminded me of [some art gallery problems](https://ieeexplore.ieee.org/document/1056648) that are also NP-complete.
delete000
CC BY-SA 4.0
2019-12-10T16:26:23.463Z
2019-12-10T16:26:23.463Z
Massimo Cafaro
<p>Especially when looking at the Knapsack problem later on, this NP-complete problem might be a good fit:</p>

<p>Number guessing, where you can only guess single numbers till you've got it right.</p>

CC BY-SA 4.0
2020-02-21T21:03:17.683Z
Could you clarify the scope of the problem you're claiming is NP-complete? Is the correct number an integer? Is the set of integers bounded?
Bash
CC BY-SA 4.0
2020-02-22T01:01:55.743Z
@SebastianGaweda Usual number guessing - I tell you that I pick an integer between 0 and $x$, ,and your job is to guess it. So you guess a number, and I answer "yes"/"no". You repeat this till you find my number, i.e. I answer "yes". The idea is that, while making $x$ e.g. 10 times bigger fairly obvious means it'll take 10 times longer to guess right, there still is a mismatch: When increasing $x$, the time to state the problem (and all relevant information) grows at worst logarithmically (e.g. if I tell you $x$ digit by digit); On the other hand, the time to solve the problem grows linearly.
Sudix
CC BY-SA 4.0
2019-07-03T19:17:35.047Z
2019-07-03T19:17:35.047Z
Sudix
<p>Mark Dominus collected a few examples of <a href="http://en.wikipedia.org/wiki/Polynomial-time_reduction">polynomial-time reductions</a> from <a href="http://perl.plover.com/NPC/">various NP-hard problems to “regular expression” matching</a>. Envisioning <a href="http://en.wikipedia.org/wiki/NP_%28complexity%29#Verifier-based_definition">polynomial-time verifications</a> isn't an enormous leap.</p>

<p>How do you illustrate the class NP-complete to undergraduates or to friends in other fields who wanted to understand the recent fuss over Deolalikar's paper?</p>

<np-hardness><big-list>
Everyday encounters with NP-complete problems
Greg Bacon
# Everyday encounters with NP-complete problems

(Asked by: username_0 on 2010-08-23)

Mark Dominus collected a few examples of [polynomial-time reductions](http://en.wikipedia.org/wiki/Polynomial-time_reduction) from [various NP-hard problems to “regular expression” matching](http://perl.plover.com/NPC/). Envisioning [polynomial-time verifications](http://en.wikipedia.org/wiki/NP_%28complexity%29#Verifier-based_definition) isn't an enormous leap.

How do you illustrate the class NP-complete to undergraduates or to friends in other fields who wanted to understand the recent fuss over Deolalikar's paper?

**Tags:** np-hardness, big-list


---

## 16 answers

### Answer by username_2 on 2010-08-24. Score: 26

My favorite example to use with non-CS friends is this one:

[Abraham, A. Blum, Sandholm. Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges. EC07.](http://www.cs.cmu.edu/~sandholm/kidneyExchange.EC07.withGrantInfo.pdf)

Kidney exchange markets are essentially a restricted form of cycle cover. I like this example because a) it's easy to explain the gist(if you leave out some of the more technical details) and b) it's one of the few instances I know of where better algorithms can literally save lives!

My second favorite example is the hospitals-and-residents problem (aka the college admissions problem). Each hospital ranks all residents (graduating medical students) and residents rank hospitals. Each hospital has a certain number of slots. From there it's a stable matching problem and can be solved in polynomial time.

But in reality, couples can enter the system (yes, there is indeed [a system](http://en.wikipedia.org/wiki/National_Resident_Matching_Program)) together, so that the system won't, for example, split up married couples who are both applying for residency. The addition of couples makes the problem NP-complete. In addition to being easy to explain, this nicely demonstrates how the introduction of long-range connections can induce NP-completeness.

> **Comments:**
> **username_3**: Great example!  David Manlove has worked extensively on these kinds of problems (both exchange and matching); the systems are being used in the UK and Hungary.  http://www.dcs.gla.ac.uk/~davidm/publications.html  As far as I know, these approaches beat the NRMP algorithms, and Eric McDermid's 3/2-approximation algorithm is the best known.  http://dx.doi.org/10.1007/978-3-642-02927-1_57  

---

### Answer by username_1 on 2010-08-24. Score: 17

Some "every day" problems that are NP-hard, appropriately formulated:

* Assigning university classes to timeslots to minimize scheduling conflicts.
* Assigning wedding guests to seats so that friends sit at the same table, but enemies do not.
* Planning a road trip to visit all of the tourist spots on a list, so as to minimize driving.


---

### Answer by username_4 on 2010-08-29. Score: 13

The traveling salesman problem is apparently accessible... at least where I am, this seems to be the most popular CS problem among non-CS folks by far. I also found the following illustration of Vertex Cover quite appealing, as introduced by my algorithms instructor:

You have a road network and wish to ensure that if a car is stuck out of fuel, there is a gas station on at least one end of the road.

As a city planner, you want to minimize costs by building the fewest number of gas stations possible. This is essentially the vertex cover problem, and I have found some success in pointing out that although you don't expect to find the optimal vertex cover in polynomial time, you can find something that is only a factor of two away in polynomial time, by simply picking up both endpoints of a maximum matching (well, that last detail might be omitted depending on how keen your audience is - especially since the MM algorithm isn't exactly a two-liner).

As for an example of a 'jump in complexity' with a small change in the nature of the problem, I think the difference between checking 2-colorability and 3-colorability makes a good example. With all the publicity surrounding the four-color theorem, one might also point out that checking whether a map can be properly colored with only three colors instead of four is hard, even though we know that it can always be colored with four colors. A fair number of people find this quite startling.

Another fairly natural situation is the [deadlock recovery problem](http://en.wikipedia.org/wiki/Feedback_vertex_set#Applications) in operating systems. This is modeled by the NP-complete problem of feedback vertex set - the smallest number of vertices whose removal makes the graph acyclic - and I find this to be a remarkable example as well (and is explained further in that wikipedia article).

> **Comments:**
> **username_5**: A *maximal* matching is enough for a two-approximation, which is much easier to compute and explain.  
> **username_4**: @Warren: Thank you for pointing that out, of course you're quite right!  

---

### Answer by username_6 on 2010-08-31. Score: 9

I think parallel parking is NP-hard.

In fact, the more general problem of finding the shortest path with bounded curvature that takes a polygonal object from its initial position to its final position in a polygonal environment is NP-hard. The proof can be found here - <http://portal.acm.org/citation.cfm?id=298976>

> **Comments:**
> **username_7**: Much much belated: the latter is a great example (though 'hard' != 'complete' of course, and I think the 'benchmark' for almost all motion planning problems is PSPACE), but now I'm curious — is the problem still formally hard if the object is convex, or even a box?  

---

### Answer by username_8 on 2010-08-23. Score: 9

Knapsack is pretty easy to grasp, especially for anyone who has had to deal with a small suitcase.. a nice example if they know dynamic programming.

Another fun (practically identical) one is Subset-sum, because it also has a nice physical interpretation: imagine the numbers being the distances of equal point-masses on an ideal (massless) ruler, with the fulcrum at the origin. Subset-sum says: does there exist a non-empty subset such that the ruler will remain balanced? (i.e., such that the center of gravity is the support point for the ruler?)

In both cases, it seems intuitive that naive strategies may force resorting to checking all subsets.

If they have more background, it's nice to grow problems by dropping constraints. For example, starting with a max flow problem, turning it into a linear program, and making it an integer program. (A great one of course is MAX-CUT, since to people with more background you can also bring up UGC; I touch some of this in an MO answer <https://mathoverflow.net/questions/33036/is-quadratic-programming-still-np-hard-if-you-have-bounds-and-a-feasible-point/33048#33048> .) Also there are neat things like problems seemingly similar which have vastly different complexity (Euler (edge) path is linear time, Hamiltonian (vertex) path is NP-complete).

> **Comments:**
> **username_3**: I like the following version of Subset Sum: you are given £10 to buy snacks from a shop.  Can you find exactly the right combination of purchases so that no money is left over?  
> **username_9**: Or just this brilliant xkcd strip: https://xkcd.com/287/  

---

### Answer by username_10 on 2010-08-24. Score: 7

Crossword puzzle construction is NP-Complete: Given a set of answers, try to fit them into a grid.


---

### Answer by username_11 on 2010-09-01. Score: 6

I created the website Tagxedo, <http://www.tagxedo.com>, a word cloud generator that fits words (sized by their frequencies) into shape. The results are very pretty, but the problem is easily proven to be NP-hard (packing problem).

Interestingly, many NP-hard problems have "easy" approximations. Tagxedo seems to be doing an almost perfect job in many cases. This leads to interesting discussion about the practical implication of P vs NP, and the topic of approximation.


---

### Answer by username_9 on 2019-12-05. Score: 5

[Refolding an unfolded origami](https://journals.aps.org/prx/abstract/10.1103/PhysRevX.7.041070) is NP-hard.


---

### Answer by username_12 on 2010-08-25. Score: 5

One of my friends spent a sabbatical year watching a baseball game in every major league stadium in North America. Without flying. (He didn't *quite* succeed; three stadiums were under construction that year.)

> **Comments:**
> **username_13**: yes, but was he trying to minimize his gas usage ? :)  
> **username_12**: Even finding a feasible schedule was NP-hard, because stadiums are not open every day (Hamiltonian cycle with time windows).  

---

### Answer by username_14 on 2017-10-25. Score: 5

Due to the success of companies like Uber and Lyft, many people have a very accessible direct experience with NP-complete problems.

> Given a collection of drivers and a list of people who want to be picked up at various times, what is the most efficient allocation of passengers to drivers?

This problem (when suitably rephrased) is NPC and I imagine that people have at some point wondered how Uber decides to pair drivers and passengers.


---

### Answer by username_15 on 2010-08-25. Score: 4

An Np-complete problem like Sudoku (on nxn sqaure) is like a Universal tool which enables us to efficiently solve all problems that have efficiently verifiable solutions. The only requirement is to have an efficient method to solve Sudoku.


---

### Answer by username_16 on 2010-08-23. Score: 4

I usually use SAT as an example. I say something like "all sorts of problems that come up all the time can be rewritten as looking for a true assignment to a big logic formula. The P vs NP question is whether is there a fundamentally easier way to solve this logic formula than just trying all possibilities. So far no one has been able to either find a way or prove that there is no easy way out".

> **Comments:**
> **username_17**: I'm not sure how many people encounter this every day.  

---

### Answer by username_0 on 2017-10-25. Score: 3

A whimsically accessible example is a [brief presentation](https://perl.plover.com/yak/Elmo/) by Mark Dominus (see the [related blog post](https://blog.plover.com/CS/elmo.html)) called “My Favorite NP-Complete Problem” where the image below is the punchline of an overview of [exact cover by 3-sets](https://en.wikipedia.org/wiki/Exact_cover).

Titles in the video series include

* *Dancing, Music, & Books*
* *Hands, Ears, & Feet*
* *Wake Up with Elmo* (about sleeping, getting dressed, and brushing your teeth)
* *People in Your Neighborhood* (about firefighters, lifeguards, and nurses)

The clear intent was for each video to contain three episodes all on a common theme drawn from a pool of topics of interest to young children.

The odd duck in the series was a video on “flowers, bananas, and … hair.”

[![Flowers, bananas, and … hair.](https://i.sstatic.net/0vvkt.jpg)](https://i.sstatic.net/0vvkt.jpg)


---

### Answer by username_18 on 2015-01-27. Score: 3

Scheduling is around us on an almost daily basis. Whether it be the workplace, manufacturing, or just planning your day, you'll find an $NP$-complete problem that you wish had an efficient exact algorithm. A situation that arises commonly in scheduling is parallel machine scheduling (typically non-preemptive, and tasks occur in parallel). A trivial way of visualizing parallel machine scheduling problems is stacking blocks.

For instance, finding an assignment of $n$ blocks of varying heights (say $p\_j$) with $m$ towers (blocks are stacked to form) with the goal of minimizing the height of the tallest tower is $NP$-hard. This is equivalent to the makespan problem on identical parallel machines (replace tasks/jobs of length $p\_j$ for blocks, towers for machines, and tallest height for the *completion time of the machine that finishes last* (called the makespan)). Asking if there is a tower of height at most $k$ would then be $NP$-complete in this situation. Observe that this doesn't need to be blocks providing we assume they can't topple over. It could be stacks of papers, crates, or plates.

Hope this helps!


---

### Answer by username_19 on 2019-12-10. Score: 2

I like to introduce Vertex-Cover as a problem in which the underlying graph models a museum, so that the vertices represent the museum rooms and the edges represent the corridors. Then, it is easy for the students to understand that minimising the number of guards required to watch over the museum corresponds to finding a vertex cover. The guards are placed at the doors of the selected rooms (vertices) and cover the corresponding corridors (edges).

> **Comments:**
> **username_9**: This reminded me of [some art gallery problems](https://ieeexplore.ieee.org/document/1056648) that are also NP-complete.  

---

### Answer by username_20 on 2019-07-03. Score: -2

Especially when looking at the Knapsack problem later on, this NP-complete problem might be a good fit:

Number guessing, where you can only guess single numbers till you've got it right.

> **Comments:**
> **username_21**: Could you clarify the scope of the problem you're claiming is NP-complete? Is the correct number an integer? Is the set of integers bounded?  
> **username_20**: @SebastianGaweda Usual number guessing - I tell you that I pick an integer between 0 and $x$, ,and your job is to guess it. So you guess a number, and I answer "yes"/"no". You repeat this till you find my number, i.e. I answer "yes". The idea is that, while making $x$ e.g. 10 times bigger fairly obvious means it'll take 10 times longer to guess right, there still is a mismatch: When increasing $x$, the time to state the problem (and all relevant information) grows at worst logarithmically (e.g. if I tell you $x$ digit by digit); On the other hand, the time to solve the problem grows linearly.  

---

