I am a bit confused with the following: We know that if P = NP then the TSP problem can be solved in polynomial time, whereas if P != NP there is no polynomial time approximation algorithm.
The question which is where I am stucked as well is how could some transform from one instance of the TSP into the other instance of the TSP in polynomial time?
I am confused on how to start or think about the problem.
Thanks.
The time required for an exact solution of the travelling salesman problem has non-polynomial growth as the number of nodes to visit increases.
But it's still possible to form an approximate solution in polynomial time. For example a simple greedy algorithm (join the nearest nodes together) gives an approximate answer in polynomial time, which is often the same as the exact answer. For example, if all the nodes are arranged in a circle this will solve the problem exactly.
$P\neq NP$ is an unsolved problem, but it is not related to whether this problem can be solved approximately but exactly in polynomial time.