4 ms·
Say 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 instan
by lkozma 15y ago
Say 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.