4 ms·
I have to be missing something here. Isn't it obvious that any discrete, single use, path location traversal can be transformed into the tsp by making every poi
by joshAg 15y ago
I have to be missing something here. Isn't it obvious that any discrete, single use, path location traversal can be transformed into the tsp by making every point on the path a node connected to it's nearest neighbors? Is the newsworthy point that some games do not require every point to be visited?
- lkozma 15y agoSay you want to prove your problem A is NP-hard and you know already that problem B is NP-hard. The fact that you can transform every instance of A to an instance of B does not prove anything, because it could be that you only create instances in a subset of B that are easy. To prove that A is NP-hard, you have to do the opposite. Show how you transform every instance of B into an instance of A, so that a solution of A implies a solution of B. Then if you had a solver for A, you could use it to solve B, which is impossible unless P=NP (since B is known to be NP-hard). In this case, you have to transform TSP to Pac-Man, not the other way around. Some technicalities aside (which are important, nevertheless), this is how hardness proofs go, sorry if it was a bit obscure.
- adgar 15y agoTo explain it even easier: every integer addition problem can be transformed into a TSP problem, but not vice-versa.
- joshAg 15y agothat would be an awesome entry into a rube goldberg contest...
- adgar 15y agoBasic start to a rigorous solution: Input: A, B : integers Output: directed graph G(V, E, w) (V = vertices, E = edges, w = weight fn) V = {c1, c2, c3} E = {(c1, c2), (c2, c3), (c3, c1)} w(c1, c2) = A w(c2, c3) = B w(c3, c1) = 0 shortest tour is the only valid tour whose length is clearly A + B.
- joshAg 15y agoPerfect thanks! not obscure at all; i did the inverse of the transform i was supposed to do. Now it's clearer why he used a form of Pacman where pacman could only visit each node once, and why it's not as trivial as i made it seem.