Re: Discussion about transformation TSP to UniqueTSP

From: "Radoslaw Hofman" <radekh@xxxxxxxxx>
Date: Wed, 29 Nov 2006 10:14:15 +0100

Uzytkownik "deepakc" <deepakc@xxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1164787821.263354.258940@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

So given Q = Q1 U Q2 U Q3 U Q4 U.....U Qn, and if it is given that Q is
NP-Complete, and given that each of Qi ! = NULL forall i in [1,N], then
we can conclude that....each Qi forall is NP-Complete, i in [1,N].

No :). Proof by counter example:

Q1 - SAT language
Q2 - 2SAT language

Q2 is "subset" of Q1.

Q1 is NP-complete, Q2 is in P.

Cheers,

Radek Hofman

.

Follow-Ups:
- Re: Discussion about transformation TSP to UniqueTSP
  - From: deepakc

References:
- Re: Discussion about transformation TSP to UniqueTSP
  - From: Bryan Olson
- Re: Discussion about transformation TSP to UniqueTSP
  - From: deepakc
- Re: Discussion about transformation TSP to UniqueTSP
  - From: Bryan Olson
- Re: Discussion about transformation TSP to UniqueTSP
  - From: deepakc

Prev by Date: Re: grammar q
Next by Date: Re: Discussion about transformation TSP to UniqueTSP
Previous by thread: Re: Discussion about transformation TSP to UniqueTSP
Next by thread: Re: Discussion about transformation TSP to UniqueTSP
Index(es):
- Date
- Thread

Relevant Pages

Re: Discussion about transformation TSP to UniqueTSP
... union is NP-Complete, but neither of the two is NP-Complete. ... Language Q1 is the ... set of strings that begin with a '1', ...
(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)
Re: non-NP-completeness of block ciphers?
... A NP-complete problem is a language that is NP-complete. ... you chose some set (the set of keys K such that blah blah blah) but ... that the set of keys K that are consistent with,..,is ...
(sci.crypt)
Re: Discussion about transformation TSP to UniqueTSP
... I can show a counter-example ... union is NP-Complete, but neither of the two is NP-Complete. ... Language Q1 is the ...
(comp.theory)
Re: Discussion about transformation TSP to UniqueTSP
... "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 ... non-empty proper subset of Q, and is decided, in linear time, by a TM ... I have to disagree with u, for the same reason I disagree with Mr. Anuj ...
(comp.theory)