Cheap and Secure Web Hosting Provider : See Now

[Answers] Are non-trivial sets formed by set operations on NPC sets still in NPC?

, , No Comments
Problem Detail: 

I know that from this answer to a question on the class NPC, that NPC is not in general closed under intersection and union. However, the answer used languages which form trivial languages under these set operations and trivial languages are of course not NP-complete. If the intersection or union is non-trivial, does the result still hold? Also, I'm also wondering about the Cartesian product of two NP-complete languages since that is another set operation.

Asked By : Ari

Answered By : Ari

Non-trivial sets formed from the unions and intersections of NP-complete sets are also not necessarily NP-complete (of course this is all under the assumption that P != NP).

Let $L$ be a NP-complete language, $A$ be any set in P, and $B:= {\{0,1\}}^*$. Then the following sets are all NP-complete since they are just the disjoint unions of a sets based on $L$, $A$, and $B$.

$L_1 := 00L \cup 01A$

$L_2 := 11L \cup 01A$

$L_3 := 01L \cup 10B$

$L_4 := 10L \cup 01B$

Then $L_1 \cap L_2 = 01A$ and $L_3 \cup L_4 = 01B \cup 10B$ These results are both in P and and non-trivial sets.

On the other hand, as mentioned in a comment above, the Cartesian product of two NP-complete sets is always NP-complete: If $X$ and $Y$ are two NP-complete sets then $X \times Y$ is in NP since a NP-witness for $(x,y) \in X \times Y$ is simply a witness for $x \in X$ along with a witness for $y \in Y$. Furthermore, the map $x \rightarrow (x,y_0)$ is a polynomial time reduction from $X$ to $X \times Y$ where $y_0$ is a fixed member of $Y$.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback