Re: Discussion about transformation TSP to UniqueTSP

Bryan Olson wrote:
You think that if the union of two languages is NP-Complete,
then each of the two NP-Complete? Note that is Q is the
union of Q and the empty language.
--
--Bryan

Hmmm...in my opinion, if the Union of 2 languages is NP-Complete, then
each of them has to be NP-Complete, PROVIDED that each language !=
NULL.

So given Q = Q1 U Q2 U Q3 U Q4 U.....U Qn, and if it is given that Q is
NP-Complete, and given that each of Qi ! = NULL forall i in [1,N], then
we can conclude that....each Qi forall is NP-Complete, i in [1,N].

Forgive me, I am not an expert in complexity Theory (I completed my
Bachelors 3 yrs ago), but that sounds correct to me.

The reason is that from Set Theory, if I have the Union of 2 or more
NON-EMPTY sets, and given that that the Union has a property X, then I
can conclude with 100% certainity that each of those sets have the
property X.

Pls correct me if I am wrong....I may be wrong, and I would like to
learn from ur expert opinion, on what is the Truth !!

.

Relevant Pages