Re: Discussion about transformation TSP to UniqueTSP

Radoslaw Hofman wrote:
Uzytkownik "deepakc" <deepakc@xxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1164787821.263354.258940@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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].

No :). Proof by counter example:

Q1 - SAT language
Q2 - 2SAT language

Q2 is "subset" of Q1.

Q1 is NP-complete, Q2 is in P.

Cheers,

Radek Hofman

Yes Radek, U are right.

But I am also right regarding my EXACT-TSP proof....I just need to
modify my sentence to include the word "non-intersecting sets" as:

So what I have written below is TRUE:

Given Q = Q1 U Q2 U Q3 U Q4 U.....U Qn, and the following facts are
known:
FACT 1: Q is NP-Complete
FACT 2: Qi ! = NULL forall i in [1,N]
FACT 3: Qi for all i in [1, N] are NON-INTERSECTING sets

then we can conclude that each Qi is NP-Complete for all i in [1,N]

.

Relevant Pages