Re: Discussion about transformation TSP to UniqueTSP


Uzytkownik "deepakc" <deepakc@xxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1164792084.120537.151270@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Radoslaw Hofman wrote:
Given Q = Q1 U Q2 U Q3 U Q4 U.....U Qn, and the following facts are
known:
FACT 1: Q is NP-Complete
FACT 2: Qi ! = NULL forall i in [1,N]
FACT 3: Qi for all i in [1, N] are NON-INTERSECTING sets

then we can conclude that each Qi is NP-Complete for all i in [1,N]

I would be more carefull - conclusion could be that at least one of this
languages is NP-complete. Getting back to TSP - if you have 3 languages:
Q1: asking about tour < C
Q2: - '' - ==C
Q3: - '' - >C

Then their union MAY contain question about tour </=/> or combination of
this relations: <=/>=/<> or <>= (meaning lower or greater or equal). Last
version is easiest - it needs O(1) to give answer "YES". Rest can be
considered as NP-complete if we ask for non-trivial C.

In opposite direction - if union is NP-complete then at least one language
it consists of is NP-complete... Because union may contain questions written
in this particular language and if we add set of easier to solve languages
then still lower bound defined as worst minimal time is the same.

Cheers,

Radek Hofman


.

Relevant Pages

  • Re: Discussion about transformation TSP to UniqueTSP
    ... Radoslaw Hofman wrote: ... presented as union of languages then some of them are NP-complete... ... "If Q is NP-Complete, and Q is Union of languages Q1...Qn, where each ... we will refer to it as the Deepak-Hofman-Bryan Theorem ...
    (comp.theory)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... deepakc wrote: ... "If Q is NP-Complete, and Q is Union of languages Q1...Qn, where each ... "If Q is an NP-Complete language, and Q1 is a non-empty proper subset of ...
    (comp.theory)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... union is NP-Complete, but neither of the two is NP-Complete. ... The cheat is that neither of the two is in NP; ... in this particular language and if we add set of easier to solve languages then still lower bound defined as worst minimal time is the same. ... Can you state precisely state you proposition -- so cheats ...
    (comp.theory)
  • Re: NP-complete and NP-Hard?
    ... There are NP-hard problems that are not in NP, ... Yes, NP-complete ... the trivial languages. ...
    (comp.theory)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... then each of the two NP-Complete? ... union of Q and the empty language. ... show that the union of Q1 and Q2 is in NPC. ...
    (comp.theory)