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."

4 of 195 comments (clear)

  1. Re:Pac-Man Was 'Solved' by UnknownSoldier · · Score: 5, Informative

    Yup, posted on /. a while back

    http://games.slashdot.org/story/10/12/03/2237200/pac-mans-ghost-behavior-algorithms

    --->

    http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior

    --->

    http://home.comcast.net/~jpittman2/pacman/pacmandossier.html

    I don't know what it is but reading about the internals of how games worked (algorithms, data structures, tricks, etc.) is neat.

  2. Re:What does the hell does NP Hard mean? by cslax · · Score: 5, Informative

    http://web.mit.edu/newsoffice/2009/explainer-pnp.html

  3. Re:What does the hell does NP Hard mean? by Anonymous Coward · · Score: 5, Informative
    More or less correct, but you are slightly confused on the definition of NP-Hard.
    • NP is the set of problems that can be verified in polynomial time.
    • NP-Hard is the set of problems which are provably at least as hard as any problem in NP (in the sense that a solution to an NP-Hard problem can be used to solve any problem in NP with only polynomial additional effort).
    • NP-Complete is the intersection of NP-Hard and NP.

      It is believed that P != NP, and if any problem that is NP-Hard (usually one just says NP-Complete) turns out to be solvable in polynomial time, then P = NP.

  4. Re:What does the hell does NP Hard mean? by Anonymous Coward · · Score: 5, Informative

    Roughly speaking, NP-hard (NP = non-polynomial) means that it scales non-polynomially fast ... e.g. if an algorithm is O(n^n) then it is NP-hard but if it is O(n^3) than it is only P-hard. By this definition, even O(n^lg(n)) is NP-hard and O(N^100) is "only" P-hard.

    No, no, no, no. NP does not mean "non-polynomial". In fact, all "P" problems are also "NP". NP means "nondeterministic polynomial", i.e, polynomial in a non-deterministic machine (think a computer with an infinite number of CPUs). It is unlikely that they are "P" ("deterministic polynomial"), but it has not been proven either way. Also, a problem being NP-hard doesn't imply that it is NP. It actually may be harder than NP: in general, to say that a problem is X-hard means that there is no problem of class X that is "harder" than it.

    For the precise definition of "harder", the wikipedia article http://en.wikipedia.org/wiki/P_versus_NP_problem is pretty good.

    (Hmm. it seems I can't log in from the comment box...)