# What's a polynomial witness for this TSP variation?

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.

• How do you conclude that "hence, it should be in NP or coNP"? – hmakholm left over Monica Aug 4 '17 at 22:56
• 1) It is a decision problem. 2) TSP is atleast as hard as the MSP variation, since MSP Turing reduces to TSP, as I've shown above. So, it has to be within the set of NP, or Co-NP languages. There's nowhere else to go. – Sohan Biswas Aug 4 '17 at 22:59
• How do you conclude "So, it has to be within the set of NP, or Co-NP languages"? I don't see how that follows from what you write before. Somewhere else for it to go would be outside NP${}\cup{}$Co-NP. – hmakholm left over Monica Aug 4 '17 at 23:00
• Fair enough, I'm fishing for ideas. The only other class it could possibly be in, is PSPACE, Where do you discern this problem to be in? – Sohan Biswas Aug 4 '17 at 23:13
• I don't know. You're the one making a claim; it's up to you to argue for it. (The problem is obviously in PSPACE, of course. But that does not tell us whether it is also in NP or coNP or both). – hmakholm left over Monica Aug 4 '17 at 23:15

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$.