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.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ I wonder if you might have misunderstood that answer. You said the languages in that answer aren't NP-complete, but that doesn't look right to me. The answer has some examples where the languages are NP-complete (and aren't just the empty language). See, e.g., the first and second bullet of that answer. So, I don't quite understand what the question is. Maybe take another look at that answer, and then update your question? $\endgroup$– D.W. ♦Aug 19, 2015 at 18:35
-
1$\begingroup$ The result still holds even for non-trivial intersections and unions. The examples are not complicated, and I encourage you to find some yourself. $\endgroup$– Yuval FilmusAug 19, 2015 at 22:50
-
$\begingroup$ @YuvalFilmus Thank you. I've thought about it and I determined a few. I don't know the SE policy- should I delete the question or answer it myself? One question though, I think that a Cartesian product of two NP-complete sets $A$ and $B$ is always NP-complete- just consider the identity function as a reduction from $A$ to $A \times B$. $f(a) = (a,b_0)$ where $b_0$ is a fixed member of $B$. Am I right? $\endgroup$– AriAug 21, 2015 at 15:57
-
1$\begingroup$ @Ari You should answer your question yourself. $\endgroup$– Yuval FilmusAug 21, 2015 at 18:23
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.