… but surprising for others e.g. traveling salesman.
A “yes” answer to the decision version of TSP (“is there a path shorter than x?”) is straightforwardly demonstrable: just specify the path. A “no” answer is not demonstrable (short of interactive provers): TSP is in NP, not coNP. And an answer to the optimization version of TSP (“find the shortest path”) is also not demonstrable (short of interactive provers): it’s FP^NP-complete, which is stronger than NP. So I don’t see any surprises there.
A “yes” answer to the decision version of TSP (“is there a path shorter than x?”) is straightforwardly demonstrable: just specify the path. A “no” answer is not demonstrable (short of interactive provers): TSP is in NP, not coNP. And an answer to the optimization version of TSP (“find the shortest path”) is also not demonstrable (short of interactive provers): it’s FP^NP-complete, which is stronger than NP. So I don’t see any surprises there.