# Tag Info

Accepted

### How is the traveling salesman problem verifiable in polynomial time?

NP is the class of problems where you can verify "yes" instances. No guarantee is given that you can verify "no" instances. The class of problems where you can verify "no" instances in polynomial ...
Accepted

### If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

For 9x9 Sudoku, no. It is finite so can be solved in $O(1)$ time. But if you had a solver for $n^2 \times n^2$ Sudoku, that worked for all $n$ and all possible partial boards, and ran in polynomial ...

### If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

It is indeed possible to use a general Sudoku solver to solve instances of TSP, and if this solver takes polynomial time then the whole process will as well (in complexity terminology, there is a ...
Accepted

### Why the need for TSP solvers when there are SAT solvers?

TL;DR: polynomial reduction increases the size of a problem; using a specific solver allows you to exploit the structure of a problem. When you reduce one NP-complete problem to another one, the size ...
Accepted

### Shortest path between two points with n hops

If vertices can be visited more than once, then yes: you can create $n+1$ copies of the graph, with each vertex $v$ in the original graph becoming the $n+1$ vertices $v_1, \dots, v_{n+1}$ and each ...
Accepted

### Linear Path Optimization with Two Dependent Variables

You can consider the 1D-position of the 2 runners as one 2D-position. X-coordinate and Y-coordinate for respectively runners 1 and 2. So in your instance, the starting point is (0, 100). Then all ...
Accepted

### Standard ILP Formulation of Travelling salesman problem: Purpose of subtour elimination constraints?

Consider this example: Every vertex has one incoming and one outgoing edge, so it is not prevented by the first two constraints. It is however prevented by the third constraint, as if you take any of ...
Accepted

### Space complexity of Travelling Salesman Problem

The brute force solution enumerates all permutations. You can easily encode each permutation using $n\log n$ bits, since you can encode it as a list of numbers from $1$ to $n$, and each number takes \$\...
Accepted

### Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP

Here is an excerpt from the introduction to an earlier paper of Svensson, Tarnawski and Végh, which was the first to give a constant factor approximation algorithm for ATSP: Without any assumptions ...

### What is the shortest total path between pairs of points?

This appears to be a maximum matching problem. Well, minimum matching, but you should be able to make the necessary adaptations.