2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How do you conclude that "hence, it should be in NP or coNP"? $\endgroup$ – Henning Makholm Aug 4 '17 at 22:56
  • $\begingroup$ 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. $\endgroup$ – Sohan Biswas Aug 4 '17 at 22:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Aug 4 '17 at 23:00
  • $\begingroup$ 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? $\endgroup$ – Sohan Biswas Aug 4 '17 at 23:13
  • $\begingroup$ 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). $\endgroup$ – Henning Makholm Aug 4 '17 at 23:15
2
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I know this, and it doesn't answer my question regarding the variation. I mentioned that the variation, i.e. Minimum Salesman Path (MSP) is either in NP, or Co-NP. $\endgroup$ – Sohan Biswas Aug 4 '17 at 22:49
  • $\begingroup$ A decision problem that is Turing reducible to a NP-Complete problem (TSP), but is not in NP. Are there more known examples of this in the literature on complexity? $\endgroup$ – Sohan Biswas Aug 5 '17 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.