[deong]

Yep. And there are the formal optimality gaps like "this algorithm provably finds a solution in polynomial time no less than twice the optimum tour length", and there are also the informal "I have no proof of anything, but this algorithm usually finds optimal tours or tours within 1% of optimality on problems of up to 10 million cities" type of gaps. Both are useful to know and understand in practice.

If my job were to solve TSP instances, I'd not bother trying to tell someone why it's hard. I'd through Iterated Lin-Kernighan or something similar at it and go get some lunch.