# What complexity class does this variation of traveling salesman problem belong to?

Given a TSP instance $T$, decide whether changing the city coordinates by adding a vector of coordinates $v$ will change the optimal TSP objective by atleast $x$. The city coordinates are integers.

The problem is in PSPACE but even the verification problem seems to be NP-hard. Is that true?

If the verification problem is NP-hard, what exact complexity class does this problem belong to?

• What do you mean by "adding a vector $v$?" – templatetypedef Jul 14 '12 at 0:16
• By that I mean, we have the original vector $c$ of coordinates for the cities and we modify the coordinates by adding vector $v$ to $c$ where $v$ is also a vector of coordinates. – dpll Jul 14 '12 at 0:18
• I expect that this is a tough question. Even the decision version of the usual Euclidean TSP (the traveling salesman problem where each city is a point on the plane and the distance between two cities is given as the Euclidean distance between the points, and your task is to decide whether there is a route whose length is at most a given threshold K) is not known to belong to NP for a reason which has nothing to do with the difficulty of TSP (Garey, Graham, and Johnson 1976 and Sum of Square Roots). – Tsuyoshi Ito Jul 14 '12 at 22:59

I'm assuming that you're thinking of the Euclidean traveling salesman problem, where $c$ and $v$ are vectors in $\mathbb{Z}^{2n}$, with two coordinates for each city. Let $minTSP(c)$ denote the length of the minimum traveling salesman tour for the cities with coordinates $c$. Then your problem asks whether $$minTSP(c + v) \ge min TSP(c) + x.$$ But then the special case $c=0$ is equivalent to asking whether $minTSP(v) \ge x$, which is coNP-hard.
• No, there are $n$ cities, each represented by two coordinates, so there are $2n$ coordinates altogether. – JeffE Jul 15 '12 at 15:54