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.