Re: Discussion about transformation TSP to UniqueTSP

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

This is clever! But I think it is not possible, even in a broad sense.

"reasonable encodings" is one monsterous assumption!

Good theory texts will go into some detail, showing how to
build the needed encodings. It's tedious, and encoding
issues are not particularly interesting. The complexity
classes at issue are sets of languages, so all the problems
we're discussing assume some encoding of problem instances
into strings.

Tim Chow offered the same counter-example in <456da3e4$0$24622$b45e6eb0@xxxxxxxxxxxxxxxxxxxxxxxxx>. Maybe
you'll like his wording better.


You are obviously
a formalist. ;-p

Not really. As long as everyone understands the formalism,
there's no problem with talking informally. Things go awry
when people start trying to reason about these things without
understanding what the informal terms actually stand for.


A second, slightly stronger objection to that same given, is that Q2 is
the union of all languages,

It really isn't.


even Q1 (reduce, toss the first bit, and
for that matter, the TM, convert the whole thing to its "contained
string").

Why are you tossing and converting things like that?


[...]
Why is it that if there is a single NP problem that is not NPC, then
P=NP? I know I've read the statement but not the reasoning.

If you understood the reasoning, you'd see that you have things
kind of backwards.


--
--Bryan

.

Relevant Pages

  • Re: Common Lisp from a Unix perspective - barriers to using CL
    ... This is quite a strange situation: some important facilities ... that Common Lisp does *not* include built-in, ... Most modern programming languages ... Because the world nowadays uses strings, ...
    (comp.lang.lisp)
  • Re: Windows vs. Linux
    ... Rather than thinking in bytes and the like when inserting an EOL marker, ... level languages like Python... ... Or forget to use raw strings. ... backslash escape character story is not quite well-chosen. ...
    (comp.lang.python)
  • Re: An argument against modus ponens
    ... languages do not have access to local weather forecasts. ... But they DO have truth-values, ... when you PRESUME that the truth of some sentence could somehow be ... These strings OCCUR IN A CONTEXT ...
    (sci.logic)
  • Re: How come Ada isnt more popular?
    ... only or get the comfort of unbounded strings. ... It's easier to do simple things with languages that have lists in ... family (including Ada). ...
    (comp.lang.ada)
  • Re: OOs best feature survey results
    ... Dynamic languages can be typed, ... BTW numerical is a type and string is another type. ... They don't map to my head, ... > Convert them to XML if you want to see strings. ...
    (comp.object)