# Re: Discussion about transformation TSP to UniqueTSP

deepakc wrote:
Hi,

Does it make any difference? We can transform every NP problem to HC
and then build TSP with question PATH==N, that means that every NP
problem can be transformed to version having == in question.

In mine opinion <= is used to show that we are asking for optimal tour
instead of tour of size N, but it does not matter for me.

Cheers,

Hmmm, yes u're right !!
somehow it escaped me.

I had second thoughts, and now I think what you wrote above might be
wrong. The reason is suppose Mr. X gives me an original TSP and asks me
"Does there exist a TSP tour of length = 1000000", where I know for
certain that there cannot be such a tour, because 1000000 is > the sum
of the costs of all TSP Edges. In that case, I can confidently give a
NO answer to Mr. X, within Polynomial time (i.e. time for summing up
all Edge costs).

So the Question is more difficult.....whether or not the YES/NO
Question is NP-Complete, actually depends on the value of C.

But one thing is for certain....is that we cannot simply say "Convert
to HCP and then get a Question of whether there is tour of length = N".
That is most probably wrong, because it means that the problem is
difficult, though it is supposed to be easy in certain cases, like what
I showed above.

I am still not sure, but that is what I think.
-Deepak

.

## Relevant Pages

• Re: Discussion about transformation TSP to UniqueTSP
... We can transform every NP problem to HC ... instead of tour of size N, but it does not matter for me. ... is greater then sum of weights then in fact we deal with different TSP ... to HCP and then get a Question of whether there is tour of length = N". ...
(comp.theory)
• Re: Discussion regarding Mr. Diabys algorithm
... TSP instance have a tour of cost <= C?"? ... I don't think it is possible to transform a TSP with multiple optima to ...
(comp.theory)
• Re: Discussion about transformation TSP to UniqueTSP
... Question is also NP-Complete, could you please let us know. ... lecture notes from MIT/Harvard/etc. ... We can transform every NP problem to HC ... In mine opinion <= is used to show that we are asking for optimal tour ...
(comp.theory)
• Re: New integer multiplication algorithm
... certificate. ... Does G have a tour of weight <= W? ... by a non-deterministic Turing machine in polynomial time. ...
(sci.math)
• Re: A variant of Traveling Salesman Problem
... > tour exist", in polynomial time, in the general case, ... Why each iteration is polynomial? ... but we still don't know how to find that shorter tour in polynomial ...
(comp.theory)