# Re: Discussion about transformation TSP to UniqueTSP

*From*: "deepakc" <deepakc@xxxxxxxxxxxxxxxx>*Date*: 28 Nov 2006 06:30:26 -0800

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

.

**Follow-Ups**:**Re: Discussion about transformation TSP to UniqueTSP***From:*Radoslaw Hofman

**References**:**Discussion about transformation TSP to UniqueTSP***From:*Radosław Hofman

**Re: Discussion about transformation TSP to UniqueTSP***From:*tchow

**Re: Discussion about transformation TSP to UniqueTSP***From:*deepakc

**Re: Discussion about transformation TSP to UniqueTSP***From:*Radoslaw Hofman

**Re: Discussion about transformation TSP to UniqueTSP***From:*deepakc

- Prev by Date:
**Re: Discussion regarding Mr. Diabys algorithm** - Next by Date:
**Re: Discussion about transformation TSP to UniqueTSP** - Previous by thread:
**Re: Discussion about transformation TSP to UniqueTSP** - Next by thread:
**Re: Discussion about transformation TSP to UniqueTSP** - Index(es):