News for hackers. Stuff that matters.
Re:Pac-Man Proved NP-Hard by kd0amg on Friday January 27, 2012 @08:43AM (#3518199)
Packman's scoring is based on collecting items and is not time dependent.

The author does not bring completion time into this at all. He reduces (a still NP-complete subset of) Hamiltonicity to the question of whether a Pac-Man level can be completed without dying.

There are no comments on this comment yet.