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