Pac-Man is NP-Hard

Pac Man Cross Stitch by Everyspoon, on Flickr

Giovanni Viglietta at the University if Pisa has published a paper in which he classifies games from the 1980s and 90s including Pac-Man, Doom, Tron and many others. Each game is evaluated and categorised according to what the player can and must do to complete the game. The paper gives a number of proofs showing that any video game with specific game-playing properties falls into a certain complexity class and uses this to classify each game. Having classified these, games are compared to assess computational hardness and determine whether each game is complete.

Pac-man is a 'location traversal' game because it involves a player moving through a landscape collecting tokens.  Graph theory is used to prove that such games are NP-hard.

Interestingly, he is quoted saying that this kind of analysis is unnecessary for modern games: "Most recent commercial games incorporate Turing-equivalent scripting languages that easily allow the design of undecidable puzzles as part of the gameplay".

Much more detail in the full report over at Technology Review: 'Pac-Man Proved NP-Hard By Computational Complexity Theory'.

The full paper, with the title "Gaming Is A Hard Job, But Someone Has To Do It!" is available in the arxiv.