Re: Discussion about transformation TSP to UniqueTSP

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.

.