# Show that the decision version of the Traveling Salesman problem is in NP

Given a graph G = (V, E) with edge lengths c : E → R, and a number d ∈ R, is there a Hamilton cycle of length l ≤ d in G? Show that the Travelling-Salesman problem is contained in the complexity class NP.

I am somewhat struggling with this exercise because I have little problem understanding the formality. I know that we need to show that there is a polynomial algorithm which verifies a given solution which we refer to as "certificate". But what exactly is the certificate here? Is it a given path (which would be easy to verify since you only have to check whether the nodes are adjacent and the costs are ≤ d) or is it just d and we have to check whether there exists a path ≤ d? But the latter is not verifiable in polynomial time as it is requires n!.

TSP can be expressed as a decision problem and an optimisation problem.

Here, as you said, a solution to the optimisation problem can be seen as a certificate to the decision problem: if you are given a certain path in $$G$$, you can verify in polynomial time that:

1. it is a Hamiltonian cycle;
2. its weight is lesser or equal to $$d$$.

That's enough to prove that TSP $$\in\mathsf{NP}$$.

Definition of an NP problem: An NP problem is a decision problem, which means for every instance there is an answer, either “Yes” or No”. For each yes-instance there is a polynomial size correct certificate. And there is a program which given an instance and a certificate will tell you in polynomial time “Yes” if given a yes-instance and a correct certificate, and “don’t know” if it is a yes-instance with an incorrect certificate, or a no-instance.

It’s up to the person trying to prove that a problem is in NP to define what the certificate would be. For example for the travelling salesman decision problem the order in which to visit nodes seems a good choice for a certificate.

(What would be an incorrect certificate? For example an order to visit nodes in, with total distance more than required).

For TSP, the problem is “is there a tour with length <= K”. The similar problem “Does the shortest tour have length exactly K” will have problems defining and finding a certificate.