[chengsun]

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.

[taneq]

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.