3 ms·
Pedantry: you can reduce TSP to SAT just because it's in NP. It's the opposite reduction (from SAT to TSP) that you can do because TSP is NP-complete.
by sweeneyrod 7y ago
Pedantry: you can reduce TSP to SAT just because it's in NP. It's the opposite reduction (from SAT to TSP) that you can do because TSP is NP-complete.