3
$\begingroup$

Is there any puzzle or game which cannot be decided in polynomial time and whose problem description can be easily understood by a kid? If it is a fun puzzle so much the better.

I want to demonstrate to a high school student the difference between P and NP class of problems using an example. Also, if there's some simple algorithm to show that it can be decided in polynomial time by a non-deterministic machine that would be a great bonus.

$\endgroup$
  • 1
    $\begingroup$ NP doesn't mean non-polynomial. Assuming you actually mean NP and not something else, all of Cook's NP-complete problems are simple enough that their statement can be understood by any reasonably intelligent high-schooler. I'm not sure what you mean with the rest of your question. $\endgroup$ – quicksort Mar 2 '17 at 14:11
  • $\begingroup$ The first thing to bear in mind is that there's no such thing as a "P algorithm" or an "NP algorithm." P and NP are classes of computational problems. In particular, this means that it's not enough to demonstrate an algorithm with super-polynomial running time, since one can find such an algorithm for any problem (it might be a bad algorithm for that problem but it's still an algorithm). Also, note that the hallmark of problems in NP is that there is an algorithm that essentially uses nondeterminism to guess the answer and then deterministically checks that the guess is correct. [...] $\endgroup$ – David Richerby Mar 2 '17 at 15:56
  • $\begingroup$ [...] Anyone who's familiar with P and NP really ought to know that so, without wishing to sound derogatory, maybe you're not the best person to give the talk you're planning on giving? It seems that you're confused about even the basic definitions and properties of P and NP. $\endgroup$ – David Richerby Mar 2 '17 at 15:57
  • $\begingroup$ You can have them 3-color a planar graph. $\endgroup$ – Yuval Filmus Mar 2 '17 at 17:13
2
$\begingroup$

There is a list of a bunch of games that are NP-hard here: https://www.ics.uci.edu/~eppstein/cgt/hard.html You might also enjoy this list of Nintendo games that are NP-hard: https://jeremykun.com/2012/03/22/nintendo-np-hard/.

Some well-known games that can be proven to be NP-hard (in some form or other) include Tetris, Minesweeper, Checkers, Chess, Dots and boxes.

I think Dots and Boxes might be a particularly surprising and accessible one -- it's rather mind-blowing that such a simple-seeming game hides such complexity.

Caveat: do understand that in many of these cases, we're actually considering a variant of the game. Many games are finite, so there are only finitely many positions, and thus can't literally be NP-complete -- so instead we consider variants. For instance, instead of chess on a 8x8 board we consider a variant with a $n \times n$ board, or something like that. The general point still applies but there are technical details that you should make sure you understand before using this in a classroom.

$\endgroup$
2
$\begingroup$

One example that's familiar to many people is dishwasher loading. You have a set of items (3-dimensional objects) you want to fit in a dishwasher. Many people have experienced that greedy methods and heuristics don't work: you load up the dishwasher using some sensible method and things don't fit. But then if you start from scratch and load things slightly differently, there's plenty of room.

The dishwasher example is nice because it's relatively familiar, and gives some intuition about why NP hardness problems are really hard: fitting things nicely locally doesn't necessarily give a good global solution. It's also truly an NP-hard problem, even in very simple cases (like all your dishes are cubes).

It's obvious that an NP machine can solve dishwasher loading in polynomial time (as it can try all ways of loading the dishwasher non-deterministically). On the other hand, most natural NP-hard problems can be solved using something like this so I'm not sure if that's the structure you want.

A second example that's likely even more familiar is three-dimensional pathfinding. Many people have experienced the struggle of (say) trying to move a couch into a new apartment. Shortest path in three dimensions in general is NP-hard (see New Results on Shortest Paths in Three Dimensions by Mitchell and Sharir for example). Some disadvantages of this problem are that the technical aspect is more difficult, and that everyday cases are often easy. (Aside from moving couches into small apartments I solve 3-dimensional shortest path every day without much issue.)

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