# 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 NP-complete, Q2 is in P, and Q1 and Q2 are both non-empty, then Q1 must be NP-hard.

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 non-empty) 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.

.

**Follow-Ups**:**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

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

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