Re: Discussion about transformation TSP to UniqueTSP

Radoslaw Hofman wrote:
"Bryan Olson" wrote:
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.

Hmmm... no. Q1 is easy to decide in some cases, but deciding
it in general is equivalent to the halting problem. To decide Q1:

If the first symbol is not '1', then (easy) say 'no';
If the first symbol is '1', and what follows is not a TM,
then (easy) say 'no';
If the first symbold is '1', and what follows is a TM, then
solve the halting problem for the TM (undecidable in general).

Q2 starting with 1 is... what? You have written what it is not, but what it is?

No; Q2 is a language -- a set of (finite) strings. It is exactly
the set of strings that I stated it is:

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.

Those are the strings in Q2. Any other strings are not in Q2.

If it is meant to be opposition of Q1 then without some unification rules you would have obtained contradiction.

No; a language is a set of (finite) strings. Q2 is the set of
strings I stated to be Q2. As I noted I'm assuming we have
defined reasonable encodings, by which I meant encoding of TM's
into strings, and graphs into strings, and strings are over some
finite set of symbols -- an alphabet. And of course a reasonable alphabet has more than one symbol. All this is so standard I saw
no reason to bloat my exposition rehashing it.

It isn;t said that you can merge without any additional steps anything...

Languages are sets of (finite) strings. "Union" is well-defined
on sets. All the terminology is well-defined and I've left
nothing ambiguous except for assuming well-defined encodings,
which we know to be available.

"Merge" is a procedure, which may be useful in computing unions and
may be built from computationally simpler "step", but that's not
at issue here. Computing the union is not the question. We only
need to know what the union of sets means, and it's perfectly well
defined. If you're unsure, look it up.

I also assume that Q2 starting with 0 is Hamilton Cycle Problem.

No, Q2 is a language. A language is a set of (finite) strings.
I said what set of strings it is. Sets do not "start" in any
well-defined sense. Sets are collections in which any candidate
for membership is either in the set or not, and that's all there
is to sets: what elements are members. No order, no multiplicity
of membership, no "starting with". I'm not inventing any of this;
you can look it up.


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

No; Q2 is not NP-Complete because Q2 is not an element of NP.
I can reduce the halting problem to deciding Q2.

Good enough? :)

Not even close.



--
--Bryan
.

Relevant Pages