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.
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.
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 resea...
> 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)
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).
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.
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.
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).
28 comments
[ 2.6 ms ] story [ 56.5 ms ] threadThere 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.
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.
If you want something specific, ask for something specific. If you specifically don't want something specifically mention you'd prefer not that.
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.
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 resea...
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)
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.
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.