(Solved): Problem 6 ( 5 points) The Traveling Salesman Problem consists of a salesman and a set of cities. Th ...

Problem 6 ( 5 points) The Traveling Salesman Problem consists of a salesman and a set of cities. The salesman has to visit cach one of the cities starting fton certain one (e.g. the hometown) and returning to the same city. The challenge of the problem is that the traveling salesman wants to minim the total length of the trip. TSP \( =\{(G, f, t): G=(V, E) \) a complete graph, \( f \) is a function \( V \times V \rightarrow Z, t \in Z, G \) is a graph that contains a traveling salesman tour with that does not exceed t). Let the HAM-CYCLE problem defined as follows: given an undirected graph \( G=\left(V^{2}\right. \), E), does there exist a simple cyele II that contai every node in \( \mathrm{V} \). Let a complete graph be a graph where there is an edge "between" every possible tuple of vertices. a- Define a certificate for TSP. Show that we can verify the certificate in deterministic polynomial time, b. Prove that the reduction of HAM-CYCLE to TSP is polynomial-time. Using the fact that HAM-CYCLE is NP-complete, what can we conclude?