What's a polynomial witness for this TSP variation?

Question

I was thinking about the Travelling Salesman Problem when I thought of a possible variation, the minimum salesman path(MSP).

In the original TSP, the question is to decide whether a path exists through the weighted graph such that the sum of the weights in the path be less than, or equal to some integer, $n$. A polynomial-time witness for this is such a given path.

In the minimum salesman path variation, I ask whether the length of the smallest path in the graph is equal to some integer, $m$ (The path satisfies the TSP route through the nodes).

If we restrict ourselves to non-negative integer values for the weights on the paths, MSP is Turing reducible to TSP. The reduction is achieved thus :

Given a weighted graph, and the value, $m$, we use an algorithm for TSP to decide whether there are any paths with length $\le m$. If yes, then we run TSP algorithm again to check whether there are any paths with length $\le m-1$.

So, MSP Turing reduces to TSP, and is a decision problem. Hence, it should be in the class $NP$, or $Co-NP$ But I am unable to find any polynomial-time witness for either acceptance, or rejection.

Can someone provide me with any?

EDIT : changed $\lt$ to $\le$ in the text.

Answer 1

Your problem is known as EXACT-TSP and lives in the complexity class DP. EXACT-TSP was proven DP-complete over thirty years ago in the paper "The complexity of facets (and some facets of complexity)" by C. H. Papadimitriou and M. Yannakakis (see Theorem 2). As such, there is no polynomial-time witness for this problem unless the polynomial hierarchy collapses to the first level.

Answer 2

TSP is in $NP$ because there are polynomial-time witnesses for path length $\le m$. But it is not known to be in Co-$NP$, because there are no known polynomial-time witnesses for length $\ge m$.

EDIT: A polynomial time witness for minimal path length $=m$ would also be a witness for minimal path length $\ge m$. Thus MSP is not known to be in $NP$.