Re: Discussion about transformation TSP to UniqueTSP



Radoslaw Hofman wrote:
Uzytkownik "Bryan Olson" <fakeaddress@xxxxxxxxxxx> napisal w wiadomosci news:inhbh.1220$Py2.445@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
If we think about language as "set of strings" then mine question is - are there possible simillar strings in Q1 and Q2?
I don't know what your term "simillar" means here.

"Similar" mean that two encoded strings (one from Q1 and second from Q2) are equal - undistinguishable.

"Equal" I understand. So the answer your question, we look at my
definitions of Q1 and Q2:

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.

So no string is in both Q1 and Q2.


If yes then, and correct answer associated with this stings are different then you cannot say that Q is union of Q1 and Q2 without some merge done.

The set of strings Q is *defined* as the union of Q1 and Q2.

Suppose that 1ABABABABAe is correct string in Q1 and 1ABABABABAe is correct in Q2

That can't happen "1ABABABABAe" is in exactly one of Q1, Q2. Since
"ABABABABAe" doesn't look like a Turing machine at all, it's Q2.


- what is it in Q?

"1ABABABABAe" is definitely a member of Q.

Or even more interesting:
Q1:
if first symbol eq '0' return NO
Q2:
if first symbol eq '0' return answer for HCP

Languages are sets of strings; they don't really "return" anything.

Well... How do you imagine "union" of this languages? It is not a union... Union means that every string from each set is also in union and we expect that ANSWER asociated with string is the same.

The union doesn't associate an answer with a string; a machine
that decides some language does. The answer is to the question
of whether the given string is in the language the machine decides.

Note the trick of my example: deciding Q means determining if any
given string is in either Q1 and Q2, but we do not have to
determine which of Q1 or Q2 it's in.


First, please precise describe what Q IS

See the definitions above.

and if it gives the same answers for the same question as Q1 and Q2.


Using your reasonong why Q is NP-complete we can easily show that Q2 is also NP-complete:
- it can check certificate in polynomial time

No you can't. When the first symbol is '1', it can be followed by
any Turing machine. You'd have to solve the halting problem.

The difference what you have here and my reasoning, is that
mine requires poly-time certificates for the Hamiltonian-cycle
problem, not the halting problem.


- any NP problem can be reduced to it

Why Q2 in your worlds is not in NP?

Because the halting problem is undecidable.


--
--Bryan
.

Relevant Pages

  • Re: Operator overloading in C
    ... All development of C as an independent language has ... making any changes or improvements to the standard ... The lack of a counted string data structure, ... Pointers can't be used for arg1 or arg2. ...
    (comp.std.c)
  • Re: syntax...
    ... B&D on the part of the language designer. ... probably handle concatenation of string literals by itself, ... bitwise XOR, or if not that, then exponentiation.) ...
    (comp.lang.misc)
  • Why C Is Not My Favourite Programming Language
    ... C has no string type. ... compiler take care of the rest. ... Why does any normal language ... the programmer fail. ...
    (comp.lang.c)
  • Re: Controlling Javascript from server side
    ... but five different language implementations here. ... 'true' means that the request must be handled asynchronously. ... There is exactly *no* reason for such a thing here. ... | percent-endoded string). ...
    (comp.lang.javascript)
  • Re: Theodore Adorno, a prophet of data systems design
    ... I have a program which reads the log file looking for leaks.) ... > The second objection is that the C language leaves certain behaviours ... the way in which C allocates arrays and fails to ... >> The ideal is in fact to be able to create a string, ...
    (comp.programming)