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

Relevant Pages

  • Re: Discussion about transformation TSP to UniqueTSP
    ... This is true because we can easily construct a polynomial time reduction ... 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 ...
    (comp.theory)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... This is true because we can easily construct a polynomial time reduction ... 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 ...
    (comp.theory)
  • Re: Operator overloading in C
    ... All development of C as an independent language has ... making any changes or improvements to the standard ... The lack of a counted string data structure, ... Pointers can't be used for arg1 or arg2. ...
    (comp.std.c)
  • Re: syntax...
    ... B&D on the part of the language designer. ... probably handle concatenation of string literals by itself, ... bitwise XOR, or if not that, then exponentiation.) ...
    (comp.lang.misc)
  • Why C Is Not My Favourite Programming Language
    ... C has no string type. ... compiler take care of the rest. ... Why does any normal language ... the programmer fail. ...
    (comp.lang.c)