Re: Discussion about transformation TSP to UniqueTSP

deepakc wrote:
Hmmm...yes the EXACT-TSP is actually NP-Complete. I too goofed up, when
I said that the NP-Completeness Question might depend on the value of
C.

It was only now when I remembered that whenever we wish to classify the
difficulty-level of a Question, we always look for the KEY-WORDS -
"worst case difficulty", and here we refer to worst case value of C.

By the way, instead of using elaborate proofs by converting into
Hamiltonian Cycle, etc.....I have a smaller and smarter proof. Please
read below:

PROOF:
It is well-known that the Question "Is there a TSP tour of length <= C
?" is NP-Complete. This Question (denoted as Q) can be converted into
the Union of 2 Questions, where the first Question (denoted as Q1) is
"Is there a TSP tour of length < C ?", and the second Question (denoted
as Q2) is "Is there a TSP tour of length = C ?".

Thus, Q = Q1 U Q2, where 'U' denotes 'Union'. From Set-Theory (imagine
a Venn-Diagram), we may conclude that as Q is NP-Complete, therefore,
both Q1 and Q2 are NP-Complete.

Hmm...I don't think I am missing anything now !!!

Your "shorter and smarter proof" is not shorter, not smarter
and not a proof.

You think that if the union of two languages is NP-Complete,
then each of the two NP-Complete? Note that is Q is the
union of Q and the empty language.

You had the Hamiltonian cycle reduction. You just seem a bit
careless about what you throw away and what you accept.


--
--Bryan
.

Relevant Pages