<p>I think I found an useful example myself!</p>

<p>Perhaps I was a little vague, but I was looking for a problem that met the following specifications:</p>

<ul>
<li>The problem itself should be easy to explain to someone studying social sciences.</li>
<li>It should have an obvious but ineffective algorithm.</li>
<li>It should have a better algorithm that is also easy to explain to someone studying social sciences.</li>
</ul>

<p>For Eulerian Cycle it's easy to explain that it's a necessary condition that every node must have even degree, but it isn't as easy to explain why it's a sufficient condition.</p>

<p>This is the problem that I think so far best meets the specification above:</p>

<p>FORM_TARGET_SET_WITH_UNIONS</p>

<p>Collection $C=\{S_1, S_2,...,S_n\}$ of sets</p>

<p>Target set $T$</p>

<p>Question: Is it possible to form target set $T$ by taking the union of some of the sets in $C$ ?</p>

<p>Obvious but ineffective algorithm:</p>

<ul>
<li>Form all $2^n$ possible unions</li>
<li>See if one of them corresponds to $T$</li>
</ul>

<p>Better algorithm</p>

<ul>
<li>Mark the sets in $C$ that are contained in $T$</li>
<li>Form the union $S_{_\cup}$ of these sets</li>
<li>If $|S_{_\cup}|=|T|$ answer $YES$, otherwise answer $NO$</li>
</ul>

<p>There is also the sister problem</p>

<p>FORM_TARGET_SET_WITH_INTERSECTIONS</p>

<p>for which the better algorithm is</p>

<ul>
<li>Mark the sets in $C$ that contain $T$</li>
<li>Form the intersection $S_{_\cap}$ of these sets</li>
<li>If $|S_{_\cap}|=|T|$ answer $YES$, otherwise answer $NO$</li>
</ul>

<p>As you can see I was looking for something really simple (almost as simple as SUBSET_PRODUCT_IS_ZERO).</p>

<p>The problem can also be contrasted with SUBSET SUM and SUBSET PRODUCT, which are NP-complete but similar in their formulation. In all these problems one is presented with a collection of objects and asked if an operation on a selection of these objects can produce a desired result.</p>

CC BY-SA 3.0
2015-07-08T18:07:44.557Z
2015-07-08T18:07:44.557Z
sixpanbass
<p>I recommend <a href="http://www.cs.tau.ac.il/~zwick/papers/jenga-SODA.pdf" rel="noreferrer">Jenga</a>!</p>

<p>Assuming you have two perfectly logical, sober, and dextrous players, Jenga is a perfect-information two-player game, just like Checkers or Go.  Suppose the game starts with a stack of $3N$ bricks, with 3 bricks in each level.  For most of the game, each player has $\Theta(N)$ choices at each turn for the next move, and in the absence of stupid mistakes, the number of turns is always between $N$ and $6N$.  So crudely, the game tree has $N^{\Theta(N)}$ states.  If you explored the game tree by brute force, you might spend exponential time to find a winning move or convince yourself that you can't win.</p>

<p>But in fact, <a href="http://www.cs.tau.ac.il/~zwick/papers/jenga-SODA.pdf" rel="noreferrer">Uri Zwick proved in 2005</a> that you can play Jenga perfectly by keeping track of just three integers, using a simple set of rules that you can easily fit on a business card.  The three numbers you need are</p>

<ul>
<li>$m =$ the number of levels (not counting the top level) with three bricks.</li>
<li>$n =$ the number of levels (not counting the top level) with two bricks side by side.</li>
<li>$t =$ the number of bricks in the top level (0, 1, 2, or 3).</li>
</ul>

<p>In fact, most of the time, you only have to remember $n\bmod 3$ and $m\bmod 3$ instead of $n$ and $m$.  Here is the complete winning strategy:</p>

<p><img src="https://i.sstatic.net/qf6Ub.png" alt="enter image description here"></p>

<p>Here I-I means you should move the middle brick from any 3-layer the top, II- means you should move a side brick from a 3-layer to the top, -I- means you should move a side brick from a 2-layer to the top, and the bob-omb means you should <a href="http://scottpilgrim.wikia.com/wiki/Sex_Bob-omb" rel="noreferrer">think about death and get sad and stuff</a>.  If there's more than one suggested move in a box, you can choose any one of them.  It's trivial to execute this strategy in $O(1)$ time if you already know the triple $(m,n,t)$, or in $O(N)$ time if you don't.</p>

<p><strong>Moral:</strong> Jenga is only fun if everyone is clumsy and/or drunk.</p>

CC BY-SA 3.0
2013-03-09T00:24:11.790Z
That's an excellent teaching example, but I would've given the +1 for the Pilgrim reference alone.
Luke Mathieson
CC BY-SA 3.0
2013-03-08T20:20:38.297Z
2013-03-09T10:06:10.677Z
2013-03-09T10:06:10.677Z
Jeffε
<p>A cashier has to return $x$ cents of change to a customer. Given the coins she has available, can she do it and how?</p>

<ul>
<li><strong>Brute force:</strong> consider all possible collections of coins and see if one of them adds up to $x$.</li>
<li><strong>Non-brute force:</strong> do it as every cashier does, by dynamic programming.</li>
</ul>

<p>There are two variants of the problem:</p>

<ol>
<li><em>Easy</em>: the cashier has unlimited supply of all denominations.</li>
<li><em>Harder:</em> the cashier has a limited supply of coins.</li>
</ol>

<p>The easy variant can be solved with a greedy algorithm. The harder one requires dynamic programming.</p>

<p>Actually, the way to present this is to propose the brute force solution, get people to understand that it is <em>very</em> inefficient, and then ask them what cashiers do, first for the easy variant, then in the hard one. You should have some examples available that go from easy to nasty.</p>

CC BY-SA 3.0
2013-03-08T23:30:15.787Z
2013-03-08T23:35:19.403Z
2013-03-08T23:35:19.403Z
Andrej Bauer
<p>To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately understandable and the trick should neither be too easy nor too hard.</p>

<p>The best I've come up with so far is</p>

<p>SUBSET_PRODUCT_IS_ZERO</p>

<p>The problem is easy to understand (given a set of integers, can a subset with product 0 be formed?), but the trick is too easy (check if 0 is among the given numbers, i.e. it's not necessary to look at a lot of subsets).</p>

<p>Any suggestions?</p>

CC BY-SA 3.0
2013-03-08T19:36:13.353Z
See: http://cstheory.stackexchange.com/questions/5188/explain-p-np-problem-to-10-year-old
Dave Clarke
CC BY-SA 3.0
2013-03-08T19:43:11.303Z
Do you want a better-than-bruteforce algorithm for an NP-complete problem or for a silly problem, like subset-product-is-0? How about the trick that does $2^{n/2 + o(n)}$ for subset sum, see e.g. the horowitz and sahni algorithm here http://rjlipton.wordpress.com/2010/02/05/a-2010-algorithm-for-the-knapsack-problem/
Sasho Nikolov
CC BY-SA 3.0
2013-03-08T19:46:42.677Z
Perhaps I didn't understand well the question, but if you need an easy understandable problem in P with an "intermediate level" polynomial time algorithm, then I suggest the classical [2-CNF satisfiability](http://en.wikipedia.org/wiki/2-satisfiability).
Marzio De Biasi
CC BY-SA 3.0
2013-03-08T19:55:39.143Z
I want an easy pedagogical example of when brute force can be avoided to contrast with easy explained np-complete problems, such as traveling salesman. I think such an example would help explain the p vs np problem for non-mathematicians.

I think 2-CNF SAT is a little too technical.

I know subset-product-is-zero is silly. That's why I'm asking for a better example. :)
sixpanbass
CC BY-SA 3.0
2013-03-08T20:02:50.980Z
Perhaps something in between SUBSET_PRODUCT_IS_ZERO and 2-CNF SAT.
sixpanbass
CC BY-SA 3.0
2013-03-08T20:22:24.767Z
... perhaps an easy-but-not-immediate one: pick two sets containing numbers in the range $1..n$ (possibly repeated) and given in casual order; decide if the two sets are equal ...
Marzio De Biasi
CC BY-SA 3.0
2013-03-09T00:29:54.630Z
How about 2-Coloring vs 3-Coloring?
Serge Gaspers
CC BY-SA 3.0
2013-03-09T12:49:11.487Z
...or Hamiltonian cycle vs Eulerian.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-03-09T17:03:11.437Z
THe way this question is written seems to presuppose that NP-complete problems can only be solved by brute force search. That would be a mistake. For instance the naive brute force search for the traveling salesman problem takes $O(n!)$ time whereas it can be solved by a non-brute-force dynamic programming algorithm in the much faster time bound $O(n^2 2^n)$.
David Eppstein
CC BY-SA 3.0
2015-07-10T02:40:36.670Z
I like giving Minimum Spanning Tree vs Minimum Steiner Tree as an example to non-mathematicians.
Yonatan N
<cc.complexity-theory><np-hardness><soft-question><complexity-classes><p-vs-np>
P vs NP: Instructive example of when Brute Force search can be avoided
sixpanbass
# P vs NP: Instructive example of when Brute Force search can be avoided

(Asked by: username_0 on 2013-03-08)

To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately understandable and the trick should neither be too easy nor too hard.

The best I've come up with so far is

SUBSET\_PRODUCT\_IS\_ZERO

The problem is easy to understand (given a set of integers, can a subset with product 0 be formed?), but the trick is too easy (check if 0 is among the given numbers, i.e. it's not necessary to look at a lot of subsets).

Any suggestions?

**Tags:** cc.complexity-theory, np-hardness, soft-question, complexity-classes, p-vs-np
> **Comments:**
> **username_1**: See: http://cstheory.stackexchange.com/questions/5188/explain-p-np-problem-to-10-year-old  
> **username_2**: Do you want a better-than-bruteforce algorithm for an NP-complete problem or for a silly problem, like subset-product-is-0? How about the trick that does $2^{n/2 + o(n)}$ for subset sum, see e.g. the horowitz and sahni algorithm here http://rjlipton.wordpress.com/2010/02/05/a-2010-algorithm-for-the-knapsack-problem/  
> **username_3**: Perhaps I didn't understand well the question, but if you need an easy understandable problem in P with an "intermediate level" polynomial time algorithm, then I suggest the classical [2-CNF satisfiability](http://en.wikipedia.org/wiki/2-satisfiability).  
> **username_0**: I want an easy pedagogical example of when brute force can be avoided to contrast with easy explained np-complete problems, such as traveling salesman. I think such an example would help explain the p vs np problem for non-mathematicians.  I think 2-CNF SAT is a little too technical.  I know subset-product-is-zero is silly. That's why I'm asking for a better example. :)  
> **username_0**: Perhaps something in between SUBSET_PRODUCT_IS_ZERO and 2-CNF SAT.  
> **username_3**: ... perhaps an easy-but-not-immediate one: pick two sets containing numbers in the range $1..n$ (possibly repeated) and given in casual order; decide if the two sets are equal ...  
> **username_4**: How about 2-Coloring vs 3-Coloring?  
> **username_5**: ...or Hamiltonian cycle vs Eulerian.  
> **username_6**: THe way this question is written seems to presuppose that NP-complete problems can only be solved by brute force search. That would be a mistake. For instance the naive brute force search for the traveling salesman problem takes $O(n!)$ time whereas it can be solved by a non-brute-force dynamic programming algorithm in the much faster time bound $O(n^2 2^n)$.  
> **username_7**: I like giving Minimum Spanning Tree vs Minimum Steiner Tree as an example to non-mathematicians.  

---

## 3 answers

### Answer by username_0 on 2015-07-08. Score: 2 | Accepted answer

I think I found an useful example myself!

Perhaps I was a little vague, but I was looking for a problem that met the following specifications:

* The problem itself should be easy to explain to someone studying social sciences.
* It should have an obvious but ineffective algorithm.
* It should have a better algorithm that is also easy to explain to someone studying social sciences.

For Eulerian Cycle it's easy to explain that it's a necessary condition that every node must have even degree, but it isn't as easy to explain why it's a sufficient condition.

This is the problem that I think so far best meets the specification above:

FORM\_TARGET\_SET\_WITH\_UNIONS

Collection $C=\{S\_1, S\_2,...,S\_n\}$ of sets

Target set $T$

Question: Is it possible to form target set $T$ by taking the union of some of the sets in $C$ ?

Obvious but ineffective algorithm:

* Form all $2^n$ possible unions
* See if one of them corresponds to $T$

Better algorithm

* Mark the sets in $C$ that are contained in $T$
* Form the union $S\_{\_\cup}$ of these sets
* If $|S\_{\_\cup}|=|T|$ answer $YES$, otherwise answer $NO$

There is also the sister problem

FORM\_TARGET\_SET\_WITH\_INTERSECTIONS

for which the better algorithm is

* Mark the sets in $C$ that contain $T$
* Form the intersection $S\_{\_\cap}$ of these sets
* If $|S\_{\_\cap}|=|T|$ answer $YES$, otherwise answer $NO$

As you can see I was looking for something really simple (almost as simple as SUBSET\_PRODUCT\_IS\_ZERO).

The problem can also be contrasted with SUBSET SUM and SUBSET PRODUCT, which are NP-complete but similar in their formulation. In all these problems one is presented with a collection of objects and asked if an operation on a selection of these objects can produce a desired result.


---

### Answer by username_8 on 2013-03-08. Score: 23

I recommend [Jenga](http://www.cs.tau.ac.il/~zwick/papers/jenga-SODA.pdf)!

Assuming you have two perfectly logical, sober, and dextrous players, Jenga is a perfect-information two-player game, just like Checkers or Go. Suppose the game starts with a stack of $3N$ bricks, with 3 bricks in each level. For most of the game, each player has $\Theta(N)$ choices at each turn for the next move, and in the absence of stupid mistakes, the number of turns is always between $N$ and $6N$. So crudely, the game tree has $N^{\Theta(N)}$ states. If you explored the game tree by brute force, you might spend exponential time to find a winning move or convince yourself that you can't win.

But in fact, [Uri Zwick proved in 2005](http://www.cs.tau.ac.il/~zwick/papers/jenga-SODA.pdf) that you can play Jenga perfectly by keeping track of just three integers, using a simple set of rules that you can easily fit on a business card. The three numbers you need are

* $m =$ the number of levels (not counting the top level) with three bricks.
* $n =$ the number of levels (not counting the top level) with two bricks side by side.
* $t =$ the number of bricks in the top level (0, 1, 2, or 3).

In fact, most of the time, you only have to remember $n\bmod 3$ and $m\bmod 3$ instead of $n$ and $m$. Here is the complete winning strategy:

![enter image description here](https://i.sstatic.net/qf6Ub.png)

Here I-I means you should move the middle brick from any 3-layer the top, II- means you should move a side brick from a 3-layer to the top, -I- means you should move a side brick from a 2-layer to the top, and the bob-omb means you should [think about death and get sad and stuff](http://scottpilgrim.wikia.com/wiki/Sex_Bob-omb). If there's more than one suggested move in a box, you can choose any one of them. It's trivial to execute this strategy in $O(1)$ time if you already know the triple $(m,n,t)$, or in $O(N)$ time if you don't.

**Moral:** Jenga is only fun if everyone is clumsy and/or drunk.

> **Comments:**
> **username_9**: That's an excellent teaching example, but I would've given the +1 for the Pilgrim reference alone.  

---

### Answer by username_10 on 2013-03-08. Score: 11

A cashier has to return $x$ cents of change to a customer. Given the coins she has available, can she do it and how?

* **Brute force:** consider all possible collections of coins and see if one of them adds up to $x$.
* **Non-brute force:** do it as every cashier does, by dynamic programming.

There are two variants of the problem:

1. *Easy*: the cashier has unlimited supply of all denominations.
2. *Harder:* the cashier has a limited supply of coins.

The easy variant can be solved with a greedy algorithm. The harder one requires dynamic programming.

Actually, the way to present this is to propose the brute force solution, get people to understand that it is *very* inefficient, and then ask them what cashiers do, first for the easy variant, then in the hard one. You should have some examples available that go from easy to nasty.


---

