Minimum offset while measuring TSP paths
It is an open problem to lower bound the difference between two distinct Euclidean TSP tours by an inverse polynomial in the input size. Such a lower bound would show that Euclidean TSP is an NP optimizaition problem, which is not known. 

Let us assume that a Euclidean TSP instance is given by a collection of points in $(\mathbb{Z} \cap [-N, N])^2$ (i.e. points with integer coordinates bounded in absolute value by $N$). It is not known how to decide the following problem in polynomial time: given two tours $T_1$, $T_2$ over the same set of points, is the cost $c(T_1)$ of $T_1$ less than the cost $c(T_2)$ of $T_2$. To solve this problem it is sufficient to upper bound $-\log |c(T_1) - c(T_2)|$ by a polynomial in n and $\log N$, which is equivalent to your question. 

The even more basic problem of deciding if $\sum_{i = 1}^n{\sqrt{a_i}} &lt; \sum_{i = 1}^n{\sqrt{b_i}}$, for $a_i, b_i \in \mathbb{Z} \cap [1, N]$ (i.e. positive integers bounded by $N$) in time polynomial in $n$ and $\log N$ is also open, see http://cs.smith.edu/~orourke/TOPP/P33.html. 

If all distances between points are rational, i.e. $\|v_i - v_j\| = a_{i,j}/b_{i,j}$ for integers $a_{ij}$, $b_{i,j}$, then 
$$
|c(T_1) - c(T_2)| &gt;= \frac{1}{\text{LCM}(\{b_{i,j}\}_{i, j \in [n]})},
$$ 
where LCM is the least common multiple function.