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.