Re: Discussion about transformation TSP to UniqueTSP

In article <456c6df5$0$568$b45e6eb0@xxxxxxxxxxxxxxxxxxxxxxxxx>, I wrote:
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.

Gerhard Woeginger pointed out to me by email that I goofed here. EXACT
TSP is the question of whether the *optimal* tour has length = C. I also
incorrectly said:

DP is contained in NP, of course

I meant to say that NP is contained in DP. Showing that DP is contained
in NP would, among other things, show that NP = co-NP.

Getting back to your question, it is certainly in NP, and I think it is
NP-complete, but I don't see immediately how to prove that.
--
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: Discussion about transformation TSP to UniqueTSP
    ... reduction from a known NP-complete language such as Hamiltonian circuit. ... where the number of cities in TSP1 is equal ... TSP tour of length=N?". ...
    (comp.theory)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... TSP is the question of whether the *optimal* tour has length = C. ... NP-complete, but I don't see immediately how to prove that. ... all the edges cost one, then add all possible edges assigning cost ...
    (comp.theory)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... Question is also NP-Complete, could you please let us know. ... lecture notes from MIT/Harvard/etc. ... We can transform every NP problem to HC ... In mine opinion <= is used to show that we are asking for optimal tour ...
    (comp.theory)
  • Re: 2007 TOUR BEGINS
    ... Funny thing is, this has been a widely circulated rumor. ... exact date, but I have heard other places, that the tour would start in ...
    (rec.music.artists.springsteen)
  • Re: NORTH KOREA TESTS NUCLEAR WEAPON
    ... replies where you say the exact same things you did 10 years ago. ... like you haven't matured any or got any wiser or even more creative ... Paul's on tour now and KISS are planning ... Outside of KISS, Peter and Ace haven't done much ...
    (rec.music.artists.kiss)