4 ms·

So you could convert TSP to SAT, solve it in SAT and get result back as optimal path? any link?

kqr 6y ago
Such is the nature of NP Complete problems, like SAT. They are the most general versions of NP problems, and all NP problems can be phrased as any NP Complete problem. I don't know if there's an established formalised terminology for this type of conversion, and I haven't found one from a quick web search. But look up something like "translate", "convert", "reduce", "encode", or the like in conjunction with "NP Complete" and you shall find what you are looking for.
- deleted 6y ago
  [deleted]
- tgflynn 6y ago
  > I don't know if there's an established formalised terminology for this type of conversion Technically they're polynomial-time many-one reductions. https://en.wikipedia.org/wiki/Many-one_reduction https://en.wikipedia.org/wiki/Many-one_reduction But in practice I think people usually just call them "reductions".
dragontamer 6y ago
The "Toy" problem is Sudoku -> 3SAT -> Solution -> Convert back. Sudoku is actually NP complete and therefore is the smallest toy example recently. N-Queens was popular before Sudoku become a thing, and you might find some basic tutorials on N-Queens -> SAT solvers. Also an easy problem that's fun to solve on your own. ------ TSP is... very complicated to reduce to 3SAT. Try it after you understand the other examples. I did a search online, and found a good set of slides here: https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/sat.pdf https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/sat.pdf The tl;dr: TSP -> Hamiltonian Cycle -> 3SAT -> Solver. http://www.math.uwaterloo.ca/tsp/sweden/index.html http://www.math.uwaterloo.ca/tsp/sweden/index.html ------ Because all NP-complete problems convert into each other, its possible to convert other NP Complete problems (ie: Sudoku) into a TSP problem, then use TSP-solvers to answer the problem. 3SAT just seems to be the one NP-complete problem that everyone's reducing to. There's an implicit assumption that its easiest to convert to 3SAT.

kqr 6y ago

Such is the nature of NP Complete problems, like SAT. They are the most general versions of NP problems, and all NP problems can be phrased as any NP Complete problem. I don't know if there's an established formalised terminology for this type of conversion, and I haven't found one from a quick web search. But look up something like "translate", "convert", "reduce", "encode", or the like in conjunction with "NP Complete" and you shall find what you are looking for.

deleted 6y ago
[deleted]
tgflynn 6y ago
> I don't know if there's an established formalised terminology for this type of conversion Technically they're polynomial-time many-one reductions. https://en.wikipedia.org/wiki/Many-one_reduction https://en.wikipedia.org/wiki/Many-one_reduction But in practice I think people usually just call them "reductions".

dragontamer 6y ago

The "Toy" problem is Sudoku -> 3SAT -> Solution -> Convert back. Sudoku is actually NP complete and therefore is the smallest toy example recently. N-Queens was popular before Sudoku become a thing, and you might find some basic tutorials on N-Queens -> SAT solvers. Also an easy problem that's fun to solve on your own. ------ TSP is... very complicated to reduce to 3SAT. Try it after you understand the other examples. I did a search online, and found a good set of slides here: https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/sat.pdf https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/sat.pdf The tl;dr: TSP -> Hamiltonian Cycle -> 3SAT -> Solver. http://www.math.uwaterloo.ca/tsp/sweden/index.html http://www.math.uwaterloo.ca/tsp/sweden/index.html ------ Because all NP-complete problems convert into each other, its possible to convert other NP Complete problems (ie: Sudoku) into a TSP problem, then use TSP-solvers to answer the problem. 3SAT just seems to be the one NP-complete problem that everyone's reducing to. There's an implicit assumption that its easiest to convert to 3SAT.