Re: Discussion about transformation TSP to UniqueTSP


Uzytkownik "Bryan Olson" <fakeaddress@xxxxxxxxxxx> napisal w wiadomosci
news:HVdbh.6211$wc5.2489@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Radoslaw Hofman wrote:
[...]
In opposite direction - if union is NP-complete then at least one
language it consists of is NP-complete...

Is that obvious?

I can (and did in a reply to deepakc) show a counter-example
that's a bit of a cheat: A union of two languages, where the
union is NP-Complete, but neither of the two is NP-Complete.
The cheat is that neither of the two is in NP; they're not
easier than NPC; they're harder.

Your example:
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.

Well.. I assume that Q1 is decidable in Omega(n) and answer is always YES.
Q2 starting with 1 is... what? You have written what it is not, but what it
is? If it is meant to be opposition of Q1 then without some unification
rules you would have obtained contradiction. It isn;t said that you can
merge without any additional steps anything...

I also assume that Q2 starting with 0 is Hamilton Cycle Problem. If yes then
Q2 is NP-complete, because for worst lower bound it is the same as any
NP-complete problem (we cen transform any NP problem to HCP and then
transform HCP to Q2 by adding '0' at beganing of instance - that is
direction to prove NP-completeness).

Good enough? :)

Cheers,

Radek Hofman


.

Relevant Pages