Slashdot Mirror
Pac-Man Is NP-Hard
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."
I'm pretty sure we knew this from actually playing the games.
Wouldn't that more be NPH-ard?
NP-hard Pacman's got nothing on Undecidable Ms. Pacman.
There is a known theorem that says: "As soon as you throw women in, nothing is decidable anymore!"
most versions of tetris use pure randomizers, faggot.
LMAO.
How can you get so emotionally involved in an algorithm used in a 20+ year old game? It's a game man. You think he is wrong about the algorithm so it is cause to call him a faggot?
You AC's crack me up sometimes. Faggot!
If the waiter brings you too much ice in your drink do you yell at him and call him a faggot too? I can hear Beavis and Butthead in the background telling you, "That was uncalled for dude".