Re: Discussion about transformation TSP to UniqueTSP
 From: Anuj Dawar <ad260@xxxxxxxxx>
 Date: Wed, 29 Nov 2006 17:43:40 +0000
Bryan Olson wrote:
Radoslaw Hofman wrote:I think what you're groping for is the following easy fact:
Because union may contain questions written in this particular language and if we add set of easier to solve languages then still lower bound defined as worst minimal time is the same.
I think I see what you mean, but that's not really a proof.
Can you state precisely state you proposition  so cheats
like mine do not apply  and prove it?
If Q = Q1 union Q2 and Q is NPcomplete, Q2 is in P, and Q1 and Q2 are both nonempty, then Q1 must be NPhard.
This is true because we can easily construct a polynomial time reduction from Q to Q1. Let a be any string in Q1 (there is such a string since Q1 is nonempty) and define the function f to map any string x to a if x is in Q2 and to x itself otherwise. f is polynomial time computable, since Q2 is in P and is easily seen to reduce Q to Q1.
AD.
.
 FollowUps:
 Re: Discussion about transformation TSP to UniqueTSP
 From: Bryan Olson
 Re: Discussion about transformation TSP to UniqueTSP
 From: deepakc
 Re: Discussion about transformation TSP to UniqueTSP
 From: deepakc
 Re: Discussion about transformation TSP to UniqueTSP
 References:
 Re: Discussion about transformation TSP to UniqueTSP
 From: Bryan Olson
 Re: Discussion about transformation TSP to UniqueTSP
 From: deepakc
 Re: Discussion about transformation TSP to UniqueTSP
 From: Bryan Olson
 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
 Re: Discussion about transformation TSP to UniqueTSP
 From: Radoslaw Hofman
 Re: Discussion about transformation TSP to UniqueTSP
 From: Bryan Olson
 Re: Discussion about transformation TSP to UniqueTSP
 Prev by Date: Re: Shortest Path Between Major US Cities (aka TSP)
 Next by Date: Re: Is there a known algorithm to solve this "playoff ranking" problem?
 Previous by thread: Re: Discussion about transformation TSP to UniqueTSP
 Next by thread: Re: Discussion about transformation TSP to UniqueTSP
 Index(es):
Relevant Pages
