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 tchowatalumdotmitdotedu
Tim,
Could U pls advise whether this Question for the TSP is also
NPComplete: 
"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
NPComplete, 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 NPComplete, 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 NPOptimization 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 NPComplete.
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
.
 FollowUps:
 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
 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
 Discussion about transformation TSP to UniqueTSP
 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):
Relevant Pages
