Pac-Man Proved NP-Hard By Computational Complexity Theory
Technology Review:
In the last few years, a few dedicated mathematicians have begun to study the computational complexity of video games. Their goal is to determine the inherent difficulty of the games and how they might be related to each other and other problems. Today, Giovanni Viglietta at the University if Pisa in Italy reveals a body of Herculean work in this area in which he classifies a large number of games from the 1980s and 90s including Pac-Man, Doom, Tron and many others.
