Re: Discussion about transformation TSP to UniqueTSP


Uzytkownik "deepakc" <deepakc@xxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1164796516.591148.244230@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Come on Radek, dont be such a spoil sport.

I am trying not to be... I know for myself - I am willing to read only
usefull things because I don't have time for interesting but meaning
nothing.

I will modify ur above statement to...
"If Q is NP-Complete, and Q is Union of languages Q1...Qn, where each
language is non-empty and non-intersecting, THEN we may conclude with
100% certainity that all of those languages Q1...Qn are NP-Complete."

I am still not sure. I can imagine situation when you make union of one
NP-complete language (SAT language for instance) and easy P language (let it
be "Finding shortest path in graph language") then their union is
NP-complete. But opposite direction reasoning is not correct - that's why I
have written then at least one element of union is NP-complete (not all of
them).

Best regards,

Radek Hofman


.

Relevant Pages