This isn't deeply suprising, once you know that TrackMania can require the user to go through a set of checkpoints in any order. This gives us a kind of "memory

This isn't deeply suprising, once you know that TrackMania can require the user to go through a set of checkpoints in any order. This gives us a kind of "memory" (which set of checkpoints we have already completed), which makes NP-completeness proofs much simpler. It's still very cute, but would apply to most racing games with that property (and the ability to force people through paths which they cannot return through).