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?