News for hackers. Stuff that matters.
Re:Pac-Man Proved NP-Hard by adgar on Thursday January 26, 2012 @07:29PM (#3516669)
To explain it even easier: every integer addition problem can be transformed into a TSP problem, but not vice-versa.
Re:Pac-Man Proved NP-Hard by joshAg on Thursday January 26, 2012 @08:14PM (#3516784)
that would be an awesome entry into a rube goldberg contest...
Re:Pac-Man Proved NP-Hard by adgar on Friday January 27, 2012 @12:16AM (#3517227)
Basic 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.