# Re: Discussion about transformation TSP to UniqueTSP

*From*: "Radoslaw Hofman" <radekh@xxxxxxxxx>*Date*: 28 Nov 2006 03:59:49 -0800

deepakc napisal(a):

tchow@xxxxxxxxxxxxx wrote:

--

Tim Chow tchow-at-alum-dot-mit-dot-edu

Tim,

Could U pls advise whether this Question for the TSP is also

NP-Complete: -

"Does there exist a TSP tour of length = C ??"

I have checked many references on Google, but they do not mention about

the "only =" version. They only state that " < = " version is

NP-Complete, i.e. "Does there exist a TSP tour of length <= C ??"

If you know any "strong" references stating that the "only =" version

Question is also NP-Complete, could you please let us know.

By strong, I mean something from some very reputed Journal, or some

lecture notes from MIT/Harvard/etc. By the way, I did a Google search

and I came across a CACHED version of one lecture note from MIT -

<http://theory.lcs.mit.edu/~madhu/FT99/lect1.ps> page 4. Here, in the

second para under the heading "3.3 NP-Optimization Problems", it says

something. Unfortunately I do not have the .PS reader in my PC (and the

above file happens to be .PS), so I am unable to read the special

symbols (like = or <=) what they are saying.

Could u please help me find some strong references, which say whether

the "only =" version is also NP-Complete.

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

.

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

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

**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

- 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):