Let's define the two variants of the Travelling salesman problem:

$TSP_{opt}$ : Give me the shortest tour

$TSP_{dec}$ : Is there a tour of $l$ or shorter (Yes/No)

Now assume $P \neq NP$:

Since $TSP_{dec}$ is NP-complete, there is no polynomial time algorithm to solve it. Now given a solution to $TSP_{opt}$ with optimal objective $l_{opt}$.

Any algorithm that can verify that this optimal solution is indeed optimal, would also answer the question is there a tour of length $l_{opt}-1$ ($#1$) or shorter. But this question is basically $TSP_{dec}$ and from the assumption $P \neq NP$ cannot be solved in polynomial time. So $TSP_{opt}$ is not in $NP$.

$#1$: for the sake of simplicity assume that the TSP only contains integer values as arc length, so the objective can only take integer values.

It was pointed out to me, that this proof has a flaw, which is not obvious to me. Where is it and from what false assumption it is coming from, so it might help people who have the same false assumption.

  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Feb 23 '16 at 20:13
  • 1
    $\begingroup$ The title for this question is awkwardly chosen; it has nothing to do with PSPACE. Also, you may want to check the definition of NP. It is trivial that $TSP_{opt}$ is not in $NP$. $\endgroup$ – Tom van der Zanden Feb 23 '16 at 20:55
  • 1
    $\begingroup$ NP is a set of decision problems. ​ ​ $\endgroup$ – user12859 Feb 23 '16 at 21:36
  • 1
    $\begingroup$ No, it fits neatly into NPO. ​ ​ $\endgroup$ – user12859 Feb 23 '16 at 21:47
  • 1
    $\begingroup$ That depends on the output requirements (if any) when there's more than one minimal tour. ​ ("Is the minimal tour length $l$?" is in DP.) ​ ​ ​ ​ $\endgroup$ – user12859 Feb 23 '16 at 21:50

Your Answer

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

Browse other questions tagged or ask your own question.