Catch up on stories from the past week (and beyond) at the Slashdot story archive

 



Forgot your password?
typodupeerror
DEAL: For $25 - Add A Second Phone Number To Your Smartphone for life! Use promo code SLASHDOT25. Also, Slashdot's Facebook page has a chat bot now. Message it for stories and more. Check out the new SourceForge HTML5 internet speed test! ×
Math

Submission + - Pac-Man is NP-hard (extremetech.com)

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."
This discussion was created for logged-in users only, but now has been archived. No new comments can be posted.

Pac-Man is NP-hard

Comments Filter:

This is the theory that Jack built. This is the flaw that lay in the theory that Jack built. This is the palpable verbal haze that hid the flaw that lay in...

Working...