Slashdot Mirror

← Back to Stories (view on slashdot.org)

Pac-Man Is NP-Hard

Posted by samzenpus on from the not-all-fun-and-games dept.

MrSeb writes "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. In a truly epic undertaking, Giovanni Viglietta of the University of Pisa has worked out the theoretical difficulty of 13 old games, 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."

2 of 195 comments (clear)

  1. I'm NP-Hard by Anonymous Coward · · Score: 0, Offtopic

    Thats what my wife said.

  2. Get a real job by Anonymous Coward · · Score: 0, Offtopic

    This is just why the Italian economy is failed.