Re: Discussion about transformation TSP to UniqueTSP




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

.