4 ms·
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!) t
by taneq 11y ago
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).
- Rafert 11y agoThat is why the Simple English Wikipedia is so great: https://simple.wikipedia.org/wiki/NP-complete https://simple.wikipedia.org/wiki/NP-complete
- chengsun 11y agoThis 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 11y agoGood 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.