Re: Discussion about transformation TSP to UniqueTSP

Patricia Shanahan wrote:
deepakc wrote:
...
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."

In our paper, we will refer to it as the Deepak-Hofman-Bryan Theorem
(DHB Theorem)

For it to be a theorem you would have to prove it.

If it were a theorem, the following simpler statement would also be a
theorem:

"If Q is an NP-Complete language, and Q1 is a non-empty proper subset of
Q, then Q1 is NP-Complete."

Let Q2 = Q - Q1, the set of elements of Q that are not elements of Q1.
Q2 is non-empty because Q1 is a proper subset. Q2 is a subset of Q, Q1
and Q2 are non-intersecting, and Q = Q1 U Q2, by construction of Q2.

According to your "theorem", Q1 and Q2 are both NP-Complete.

However, it is easy to define trivially-decidable non-empty proper
subsets of NP-Complete languages. If there is any known example X of a
specific string that is in the NP-complete language Q, then {X} is a
non-empty proper subset of Q, and is decided, in linear time, by a TM
that accepts X and rejects all other strings.

Deciding a set may be easier or harder than deciding one of its
supersets - there is no general relationship.

Patricia

I have to disagree with u, for the same reason I disagree with Mr. Anuj
Dhawar.

Let me elaborate in greater detail....and I wish that Mr. Anuj reads
this carefully too.

I refer to the example u posted above -> "If Q is an NP-Complete
language, and Q1 is a non-empty proper subset of Q, then Q1 is
NP-Complete."

U see...if Q is NP-Complete, it is IMPOSSIBLE for us to identify a
subset of Q, which is not NP-Complete.

Yes, u are correct if u said that we can identify subset-instances of Q
which are trivially decidable, but that does not mean we have
identified a subset-Class of Q which is trivially decidable.

Thats the difference between Class and an Instance. And in
complexity-theory, we give nomenclatures (or names) to CLASSES of
problems, not INSTANCES.

So if it were possible for us to identify a subset of Q that is
trivially decidable (that is not NP-complete), then Q would not be
NP-Complete in the first place.

I hope u agree.
-Deepak

.

Relevant Pages