You can always reduce anything to anything, but in this case, the reduction is relevant because it only adds a polynomial factor. Showing that a problem can be

You can always reduce anything to anything, but in this case, the reduction is relevant because it only adds a polynomial factor. Showing that a problem can be reduced to another one in polynomial time is core to proving np-completeness. That means that tsp and tso-opt are in the same ballpark of complexity. The reason tsp-opt isn't called np-complete isn't related to its complexity, but to the fact that only decision problems get to be called that. As I said, there are problems where the decision problem and the optimization problem are completely unrelated in terms of complexity, but tsp isn't one of those.