If you were never good at the 80’s classic video game Pac-Man don’t feel too bad. Giovanni Viglietta from the University of Pisa has published a research paper entitled ”Gaming is a hard job, but someone has to do it!” that provides an existence proof of a polynomial time reduction of Pac-Man to the famous Traveling Salesman Problem. For those not up on their theory of computation, this result means Pac-Man is in the complexity class NP-Hard, which means it is at least as hard to solve as the hardest problems in the class NP. In short, it is very hard to solve these problems with a computer in a reasonable amount of time.
Viglietta classifies a large number of classic video games by proving common game mechanics (features) reduce into particular complexity classes. This novel meta approach makes it easy to determine the complexity of particular video game by proving it exhibits a meta-feature, which maps it to a complexity class. Using this approach Viglietta shows the complexity class of several classic games such as:
- Boulder Dash (First Star Software, 1984) is NP-hard.
- Doom (id Software, 1993) is PSPACE-hard.
- Lemmings (DMA Design, 1991) is NP-hard.
- Lode Runner (Brderbund, 1983) is NP-hard.
- Pac-Man (Namco, 1980) is NP-hard.
- Prince of Persia (Broderbund, 1989) is PSPACE-complete.
- Tron (Bally Midway, 1982) is NP-hard.
(via Technology Review)