8

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?

sixpanbass
  • 153
  • 1
  • 9
  • 1
    See: http://cstheory.stackexchange.com/questions/5188/explain-p-np-problem-to-10-year-old – Dave Clarke Mar 08 '13 at 19:36
  • 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 Mar 08 '13 at 19:43
  • 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. – Marzio De Biasi Mar 08 '13 at 19:46
  • 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 Mar 08 '13 at 19:55
  • Perhaps something in between SUBSET_PRODUCT_IS_ZERO and 2-CNF SAT. – sixpanbass Mar 08 '13 at 20:02
  • ... 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 Mar 08 '13 at 20:22
  • 4
    How about 2-Coloring vs 3-Coloring? – Serge Gaspers Mar 09 '13 at 00:29
  • ...or Hamiltonian cycle vs Eulerian. – Mahdi Cheraghchi Mar 09 '13 at 12:49
  • 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)$. – David Eppstein Mar 09 '13 at 17:03
  • I like giving Minimum Spanning Tree vs Minimum Steiner Tree as an example to non-mathematicians. – Yonatan N Jul 10 '15 at 02:40

3 Answers3

23

I recommend Jenga!

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

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

Jeffε
  • 23,129
  • 10
  • 96
  • 163
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.

Andrej Bauer
  • 28,823
  • 1
  • 80
  • 133
2

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.

sixpanbass
  • 153
  • 1
  • 9