# Are NP-complete sets formed from two other sets only if at least one is NP-hard?

This question is somewhat of a converse to a previous question on sets formed from set operations on NP-complete sets:

If the set resulting from the union, intersection, or Cartesian product of two decidable sets $L_1$ and $L_2$ is NP-complete, is at least one of $L_1, L_2$ necessarily NP-hard? I know that they cannot both be in P (assuming P != NP) since P is closed under these set operations. I also know that the conditions of "decidable" and "NP-hard" are necessary since if we consider any NP-complete set $L$ and another set $B$ outside of NP (whether just NP-hard or undecidable) then we can form two new NP-hard sets not in NP whose intersection is NP-complete. For example: $L_1:= 01L \cup 11B$, and $L_2:= 01L \cup 00B$. However, I don't know how to proceed after that.

I'm thinking that the case of union might not be true since we can take a NP-complete set $A$ and perform the construction in Ladner's Theorem to get a set $B \in$ NPI which is a subset of $A$. Then $B \cup (A \setminus B) = A$ is the original NP-complete set. However, I don't know if $A \setminus B$ is still in NPI or NP-hard. I don't even know where to start for the case of intersection and Cartesian product.

• A problem in P can be NP-complete if P=NP, which makes your claim "they cannot both be in P" false. – Wojowu Aug 24 '15 at 18:16
• @Wojowu Thank you, you are correct. I just assumed that it was understood that this whole question is based on the premise that P != NP. Otherwise it is meaningless/trivial since we would then have NPC = P. I will edit the question. – Ari Aug 27 '15 at 16:39
• @Ari, Actually $NPC\not = P$, even if $P=NP$. – Tom van der Zanden Nov 28 '15 at 18:33
• @TomvanderZanden How is that possible? $NPC \subseteq NP$ so if P = NP then every problem in NP can be solved in polynomial time including problems in NPC. – Ari Nov 30 '15 at 13:37
• @Ari The empty set and the set of all strings are in $NP$, but they're not $NP$-complete. You can't reduce anything to the empty set (or set of all strings) because it's always a no (resp. yes) instance. – Tom van der Zanden Nov 30 '15 at 14:14

• This is a very strange definition of language intersection, different from the one that was meant here. If $L_1$ and $L_2$ are languages (such as 3SAT), by their intersection we mean $L_1 \cap L_2$. – Yuval Filmus Aug 30 '15 at 5:13
• @KyleJones@Yuval I think there might be some confusion regarding instances vs. languages. While every instance of 3SAT is certainly composed solely of Horn clauses and Anti-Horn clauses, it is not the case that the language $\mathsf{3SAT}$ equals $\mathsf{HORN3SAT}\cap\mathsf{ANTIHORN3SAT}$ or alternatively $\mathsf{HORN3SAT}\cup\mathsf{ANTIHORN3SAT}$ since these sets have instances each composed solely of Horn clauses or Anti-Horn clauses whereas each instance of 3SAT can have a mixture of these two types of clauses.. – Ari Aug 31 '15 at 16:00