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.