Re:TrackMania is NP-complete
by taneq on Friday May 13, 2016 @08:40AM
(#11690026)
It's confusingly written. In this context, I think they're saying that there's no general polynomial-time algorithm (edit: assuming P != NP, thanks chengsun!) to give you a path through a TrackMania track which will complete the track (as in, visit every waypoint in some order and then reach the finish).
[ Parent
| on HN ]
This is only true assuming that P != NP, which is still an unsolved question.
Furthermore, NP-completeness only applies to decision problems. In this case the paper explores the problem of deciding whether or not there exists a path which will complete the track.
The upshot is, if there exists a polynomial-time algorithm to decide this question, then we can use this algorithm to solve all other NP decision problems in polynomial time.
Good catch, and it'd be hilarious if such a long-standing problem were solved by some person trying to write a bot for a racing game.
That is why the Simple English Wikipedia is so great: https://simple.wikipedia.org/wiki/NP-complete