Computer Scientists often devote a great amount of time and effort in playing computer games. With the intention of legitimizing this endeavour in the name of academic research, I will focus on the algorithmic complexity of computer games. I'll begin by surveying some of the known results and outline the proof techniques, for such well known games as Minesweeper, Sokoban and Tetris.In the game of Lemmings, the player must guide a tribe of green-haired lemming creatures to safety, and save them from an untimely demise. I will describe and analyze the problem of deciding whether or not it is possible to complete a level of this game (and hence to find a solution to that level). Under certain limitations, this can be decided in polynomial time, but I will show that in general the problem is NP-Hard. I will outline my latest results, to show that this hardness holds 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.
This file was generated by bibtex2html 1.92.