Re: Discussion about transformation TSP to UniqueTSP

deepakc wrote:
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.

Hmmm...in my opinion,

Do you think the issues here are matter of 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 [... statement clarified in follow-ups]

Still not good. Let Q1 be SAT, and Q2 be the set of logical
expressions with exactly 23 variables. Q1 is in NPC; and I can
show that the union of Q1 and Q2 is in NPC. Q2 is not empty,
but we can't say Q2 is NP-Complete (it is iff P=NP).

A counter-example along different lines: Language Q1 is the
set of strings that begin with a '1', followed by a Turing
Machine that halts on empty input. Language Q2 is the set of
strings that are either
a '1' not followed by a TM that halts on empty input,
or
a '0' followed by a graph with a Hamiltonian cycle.
I'm assuming reasonable encodings are a given. The union of
Q1 and Q1 is NP-Complete. Q1 and Q2 are both non-empty, and
neither is NP-Complete because neither is even in NP.


Hmmm... a tricky case... Prove or disprove that if:
Q1 is in NP,
Q2 is in NP, and
the union of Q1 and Q2 is NP-Complete,
then either:
Q1 is NP-Complete, or
Q2 is NP-Complete
(or both).
The proposition is obviously true if P=NP, so full credit for
dis-proof under the added assumption that P!=NP.


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

I'm no expert either. And let's give the experts their due: they
were born as ignorant as were you and I. Then they did the work.


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.

Ah! That's not right, but the wording is not far from a correct
statement: If *every member* of the set union(A, B) has property
X, then every member of A has property X, and every member of B
has property X. A set having a property is different from a
member of the set, or even all members of the set, having the
property. In the complexity-theory issues here, we're talking
about properties of languages, where languages are sets of
strings.


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

Did my best.


--
--Bryan

.

Relevant Pages