TrackMania is NP-complete | Hacker News Reader

TrackMania is NP-complete

arxiv.org

77 pointshiq28 comments

The proof is not quite complete — the paper says, "given a path in the track we can check in polynomial time whether it completes the track." But this is only true if the path has length that's polynomial in the length of the track. So there needs to be an argument showing that if there is any solution to a TrackMania level, then there is one that's polynomial in the length of the track.

I think this is straightforward in the case of TrackMania but it needs to be spelled out. In other motion-planning games — for example, Sokoban — there can be levels that require an exponential number of moves.

A quick sketch of how you might argue it. There are polynomially many states for the position, heading, velocity and other attributes of the car. Although there are exponentially many states for the n checkpoints, any given run can only visit n of them (because the checkpoints cannot be reset). Hence any given path can visit at most polynomially many different states, and so for every path there's a path of polynomial length that reaches the same end state (just cut out the portions of the path between identical states). Hence if there's any path that completes the level, there's a path of polynomial length that does so.

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).

This paper would be much more entertaining with a complete example 3-SAT solver track, and a twitch stream of people trying to complete it.

100%!

Similar examples:

https://news.ycombinator.com/item?id=9022021

https://news.ycombinator.com/item?id=1315551

https://news.ycombinator.com/item?id=10317224

https://news.ycombinator.com/item?id=9645845

https://news.ycombinator.com/item?id=10574895

https://www.youtube.com/watch?v=HhGI-GqAK9c

https://bosker.wordpress.com/2013/03/13/adrift-is-np-complet...

https://arxiv.org/abs/1106.2104

https://nadamhu.wordpress.com/2013/06/14/my-ios-game-based-o...

http://www.gwern.net/Turing-complete

http://for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

(Generated by going through HN search results for Turing complete and NP complete)

Is the following correct? This proof depends on the fact that in the clause gadget (figure 5) the car can't turn once it jumps to the cheek point. Because of this, it can't in from the track for one for one variable to that for another.

Yes, that's right.

The paper doesn't explain in detail how the gadgets are assembled. But presumably the track is arranged so that from the starting point the car must enter the variable gadget for X1. The "true" branch for X1 then visits each clause gadget containing X1, and the false branch visits each clause gadget containing ¬X1. These two branches must then come together somehow (no gadget is given, but it's easy to see how to make one), and then enter the variable gadget for X2, and so on.

So if the car could steer in mid-air, then it would be able to jump from ¬X3 (say) back to X1, and this would allow it to repeat the track for the X2 and X3 variables, and it could make a different choice on the second run through, thus making its path no longer correspond to a 3SAT solution.

Thanks, that's basically how I saw it. I guess that's one way how this proof essentially makes the problem discrete (in addition to assuming perfect driving).

https://arxiv.org/abs/1411.5765

Site can't be accessed from here (Maybe overloaded with traffic?). Anyone got an archive?

near figure 5, shouldn't the clause X1 ∧ ¬X3 ∧ X4 be X1 ∨ ¬X3 ∨ X4?

Yes, that's right. 3SAT uses conjunctive normal form.

What does "NP-complete" mean? Can anyone elaborate?

https://en.wikipedia.org/wiki/NP-complete

If he wanted a Wikipedia article he would ask for one.

It's one of the most fundamental computer science topics.

There is absolutely no point in coming up with an ad-hoc explanation or copy/pasting one just to stay on HN instead of linking to a good resource.

He could at least have linked to https://simple.wikipedia.org/wiki/NP-complete instead.

I think Wikipedia is the perfect response. It gives the person actual facts (As close as they can get) instead of someone talking off the top of their head or out of their ...

If it was a question about an aspect of the topic sure Wiki page is a bad response, but if asking a large whole scale factual question send them the information.

He did, indirectly. He asked for elaboration on the point and the information on that page is a perfectly good way of elaborating on the subject.

If you want something specific, ask for something specific. If you specifically don't want something specifically mention you'd prefer not that.

I'm inclined to agree - most people here know what Google is. Asking a group of humans implies a human giving a human readable answer, not a link to an an encyclopedia article that's mostly useless unless you're a CS grad. (Funnily enough, this is acknowledged by the wiki community, looking at the box at the top of the page)

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).

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

http://alecb.me/blog/p-vs-np

NP-Complete is one of those concepts that takes quite a bit of background knowledge to get a really good handle on. Disclosure: I just finished an undergraduate Algorithm Analysis course this week, so this knowledge is fresh in my mind, I'll try to explain in the way that I learned, but do note that it may not be strictly correct academically.

When speaking about the efficiency of a program or algorithm, we frequently use Asymptotic, or "Big-O" notation [1] to describe how the time requirements of a program scale relative to its input. For example, Bubble sort is an example of an O(n^2) Algorithm[2], which means that if it takes 1 second to sort a list of size=10, then it will take roughly 10 seconds to sort a list of size=100. The reason we use Big-O notation is because it gives an idea of how the program will perform on any computer independent of other factors like processor speed.

Bubble sort is an example of an algorithm that, while not the most efficient algorithm for sorting, does take polynomial time, which means that its big-O is expressible as some O(n^k) where k is some reasonably small number (My professor says that k<=3 is what many agree as reasonable, but I'm sure that number varies). Many problems however do not have an algorithm that solves the problem in Polynomial time. To solve the Traveling Salesman Problem exactly can take O(n!) time[3], and solving the knapsack problem takes O(2^n) time[4]. Note that there are algorithms that may solve exponential problems such as these approximately, or heuristically in polynomial time, but finding the exact solution takes massive amounts of time for any decently large value of n.

It's natural to wonder why some problems are "easy" to solve, and why some are "hard" to solve, researchers have been puzzling over this for some time and have come up with a classification for "easy" and "hard" problems that they call P and NP. For the sake of this classification, we consider an algorithm to have two stages: stage 1 is where the problem is solved and a candidate answer is produced, stage 2 is where the candidate answer produced by stage 1 is verified to be a correct and valid answer to the problem. For a problem to be classified as P (which which stands for Polynomial), both stage 1 and stage 2 of its algorithm must have polynomial time requirements. On the other hand we have NP, which does not stand for Non-Polynomial like you might expect, instead it stands for Non-Deterministically Polynomial. There's a lot of theory behind this concept, but essentially it means that the only possible way for stage 1 of this algorithm to have polynomial time is to resort to non-deterministic algorithms[5], one example of which is an oracle algorithm which will instantly provide you the correct answer magically[6]. NP-complete is a term that means that once stage 1 of an NP-complete algorithm has magically produced the correct answer, stage 2 can still verify that answer in polynomial time. Also note that NP as a set of problems contains all problems in P, since even though a polynomial time stage 1 may exist, the problem still could employ a non-deterministic stage 1 also.

The first problem shown to be NP-complete was the Boolean Satisfiability Problem or SAT problem in 1971[7] which asks, given a formula consisting of boolean input statements, AND's, OR's and NOT's, is there any combination of inputs such that the result of the formula is true. Researchers soon discovered that it was possible to show other problems like the 3-CNF SAT problem are NP-complete by showing that problems could be transformed so that they could be solved directly by the SAT algorithm. A good way to think about this is that if you have an algorithm to solve mathematical addition, you could create an algorithm to solve mathematical multiplication by transforming the inputs, for example 2x3 could be transformed into 2+2+2, and this would let you solve multiplication by transforming to addition. This is how researchers today prove that a problem is NP-complete, by reducing their problem to a known NP-complete problem. An interesting side effect of this is that all known NP-complete problems today form a network of transformations, from any problem to any other problem, see [8] for an example of this. This also means that if a true Polynomial solution to ANY NP-complete problem is found, then every other NP-complete problem would also be solved automagically through transformations.

From the Abstract of the paper: "We prove that completing an untimed, unbounded track in TrackMania Nations Forever is NP-complete by using a reduction from 3-SAT and showing that a solution can be checked in polynomial time." which means that this researcher takes the TrackMania problem, and reduces it to the 3-SAT to prove that the TrackMania problem is NP-complete

Hope this helps. If anyone who knows more than me has any corrections to make, please let me know.

[1] https://en.wikipedia.org/wiki/Big_O_notation

[2] https://en.wikipedia.org/wiki/Bubble_sort

[3] https://en.wikipedia.org/wiki/Travelling_salesman_problem

[4] https://en.wikipedia.org/wiki/Knapsack_problem

[5] https://en.wikipedia.org/wiki/Nondeterministic_algorithm

[6] https://en.wikipedia.org/wiki/Oracle_machine

[7] https://en.wikipedia.org/wiki/Boolean_satisfiability_problem

[8] https://en.wikipedia.org/wiki/NP-completeness#NP-complete_pr...

This is a nice write up. One thing though:

  > Bubble sort is an example of an O(n^2) Algorithm[2], which means that if it takes 1 second to sort a list of size=10, then it will take roughly 10 seconds to sort a list of size=100.

It would take roughly 100 seconds to sort an array of size 100, if it would take 1 second to sort an array of size 10. (10 times the size ~ 10^2 times the time)

Oh, derp. Thanks for catching that. I'm not able to edit the original comment for some reason though.

Reply on news.ycombinator.com