Re: Discussion about transformation TSP to UniqueTSP

In article <1164714136.832964.38370@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
deepakc <deepakc@xxxxxxxxxxxxxxxx> wrote:
Could U pls advise whether this Question for the TSP is also
NP-Complete: -
"Does there exist a TSP tour of length = C ??"

This problem is usually called the EXACT TSP problem. EXACT TSP is
DP-complete, where DP is the class of languages L that are the intersection
of a language in NP and a language in co-NP (i.e., there exists L_1 in NP
and L_2 in co-NP such that L = L_1 intersect L_2). Note that DP is *not*
the same as NP intersect co-NP. DP is also the second level of something
called the Boolean hierarchy. DP is contained in NP, of course, but it is
not known whether DP = NP.

I think that a proof that EXACT TSP is DP-complete may be found in
Papadimitriou's book "Computational Complexity" (but I don't have a copy of
it on me right now). Also you may be able to find a proof using Google, now
that you know to search for "EXACT TSP" and "DP-complete."
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Re: Question about floats and mods...
    ... > How do some computer programs calculate the modulo of a float if ... equivalence class in number theory context (e.g., ... and no longer recall the exact syntax. ... EXCEL, it is whatever the language says it is, like in another response. ...
    (sci.math.num-analysis)
  • Re: Someone
    ... basic) in order to check my program *Binomial* exactness due to his weakness in this program language. ... After Afonso suggested to other to do exactly THAT for those who ... verify the program provided exact results he call me a LIAR. ... The error was the convention of IGNORING a LOOP before the ...
    (sci.stat.math)
  • RE: Why cant overloads take into account the return type.
    ... I think the straight answer to this question is that YES, a language can be ... implemented such that the return type can be taken into account during ... should do the same exact thing to the same exact set of inputs. ... > double FromString(string SomeValue) ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Course rules
    ... (The following is from an avid golfer who is not an expert on the exact ... language of the rules....) ... Nothing makes me madder than striping one down the middle of the ...
    (rec.sport.golf)
  • Re: Does sizeof(char) always equal to 1?
    ... >> Thank you for all your replies. ... The C language doesn't require that such a type exists. ... The C99 standard states that if an implementation has exact width 8, ...
    (comp.lang.c)