which raises the question - what is a game? is it the collection of all possible permutations of states allowed by the rules, as in the Pac-Man generalization or this extremely weird corner case SC scenario that requires extended amounts of sub-optimal play? If I -can- construct such a bizarre and entrenched StarCraft position, is it part of "the game", or is it a weird theoretical custom map whose sole purpose is proving starcraft is np-hard to "solve"
But at the same time it's fascinating that they were able to embed this sub-problem within a starcraft scenario, such that any optimal player would have to solve this NP-hard problem. This sort of argument is a classic in the field, and always fun to read.
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.
NP-Complete just means that a correct solution can be evaluated in polynomial time by a deterministic Turing machine. It says nothing of the number of solutions that exist.