I think NP-hard is correct? You can reduce the halting problem and Kolmogorov complexity computation to each other [1], so the question is whether TSP can be reduced to the halting problem. Well, you can reduce SAT to the halting problem (they explain how here [2]) and you can reduce TSP to SAT given they're both NP-complete so... we're done?
[1] https://www.nearly42.org/cstheory/halting_to_kolmogorov/
[2] https://en.wikipedia.org/wiki/NP-hardness#Examples