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 complexity class does this variation of traveling salesman problem belong to?
complexity theory;reductions;np hard;decision problem;traveling salesman