## G. Cormode.
The hardness of the lemmings game, or, “Oh no, more
NP-Completeness proofs”.
Technical Report 2004-11, Center for Discrete Mathematics and
Computer Science (DIMACS), 2004.

In the computer game `Lemmings', the player must guide a tribe of green-haired
lemming creatures to safety, and save them from an untimely demise.
We formulate the decision problem which is, given a level of the game, to
decide whether it is possible to complete the level (and hence to find
a solution to that level).
Under certain limitations, this can be decided in polynomial
time, but in general the problem is shown to be NP-Hard.
This can hold even if there
is only a single lemming to save, thus showing that it is hard to
approximate the number of saved lemmings to any factor.

[ bib |
.html |
Alternate Version ]
Back

*This file was generated by
bibtex2html 1.92.*