Re: Discussion about transformation TSP to UniqueTSP



Bryan Olson wrote:
Radoslaw Hofman wrote:

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?

I think what you're groping for is the following easy fact:

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