Can travelling salesman be translated into a SAT problem?

Question

I read that all NP-complete problems can be translated into one another.

I can't see how the travelling salesman problem which involves distances which are real numbers can be translated into a boolean satisfaction problem? Do you have to limit it to integer distances?

Is there a way to do it?

Answer 1

I don't know what all the comments are talking about, this is definitely a question in Mathematics. To answer your question, we note that real numbers aren't actually encodable by Turing Machines (if they're infinitely long), so the problem of TSP over arbitrary real numbers is not really applicable (how would you even express the input?). Over rational numbers (or any other countable subset of real numbers that is closed under addition) it can still be done since they're countable, so they can be encoded in similar ways as integers.

Also if you look at Cook's proof that SAT is NP-Complete, you'll see that he uses a reduction from the non-deterministic polynomial time turing machine that solves an NP problem, so the structure of the problem isn't really relevant.