# 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

## 1 Answer

The intersection of two non-NP-hard languages can be NP-hard. Example: The solutions of any 3SAT instance are the set intersection of the solutions of a HORN-3SAT instance and an ANTIHORN-3SAT instance. This is because a 3CNF clause must be either a Horn or anti-Horn clause and a 3SAT instance is the conjunction of such clauses. 3SAT is of course NP-complete; HORN-3SAT and ANTIHORN-3SAT are both in P.

• I can't follow your example. The intersection of HORN-SAT and ANTIHORN-SAT is a pretty boring language that is definitely in P. – Yuval Filmus Aug 29 '15 at 9:59
• HORN-3SAT can be defined in many ways. One way is to fix an encoding of HORN-3SAT instances – each string encodes some such instance – and then HORN-3SAT consists of the satisfiable instances. This encoding is likely different from the encoding you would use for ANTIHORN-3SAT, so it's not clear what the intersection language exactly is – definitely not SAT. – Yuval Filmus Aug 29 '15 at 20:29
• Another possibility is to define HORN-3SAT as the language of 3SAT instances which are (i) in Horn form, (ii) satisfiable. Now the intersection of HORN-3SAT and ANTIHORN-3SAT does make sense: it consists of all 3SAT instances which are (i) in both Horn and anti-Horn forms, (ii) satisfiable. This can only be easier than each of HORN-3SAT and ANTIHORN-3SAT. – Yuval Filmus Aug 29 '15 at 20:30
• 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