wraggster
January 27th, 2012, 00:10
An Italian researcher with a penchant for retro games — or perhaps just looking for an excuse to play games in the name of science! — has used computational complexity theory to decide, once and for all, just how hard video games are (http://www.extremetech.com/gaming/115677-pac-man-is-np-hard-same-as-travelling-salesman-problem). In a truly epic undertaking, Giovanni Viglietta of the University of Pisa has worked out the theoretical difficulty of 13 old games (http://arxiv.org/abs/1201.4995), including Pac-Man, Doom, Lemmings, Prince of Persia, and Boulder Dash. Pac-Man, with its traversal of space, is NP-hard. Doom, on the other hand, is PSPACE-hard.
http://games.slashdot.org/story/12/01/26/238244/pac-man-is-np-hard
http://games.slashdot.org/story/12/01/26/238244/pac-man-is-np-hard