Re: Discussion about transformation TSP to UniqueTSP



deepakc wrote:
Radoslaw Hofman 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,
Radek Hofman

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

Dear Radek,

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

.