Pac-Man Is NP-Hard 195
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."
nothing of value was gained (Score:4, Funny)
Re:Yeah... (Score:5, Funny)
Re:Pacman is NOTHING!!! (Score:4, Funny)
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!"
Re:Tetris isn't NP-hard anymore (Score:5, Funny)
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".