10
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ A problem in P can be NP-complete if P=NP, which makes your claim "they cannot both be in P" false. $\endgroup$
    – Wojowu
    Commented Aug 24, 2015 at 18:16
  • 1
    $\begingroup$ @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. $\endgroup$
    – Ari
    Commented Aug 27, 2015 at 16:39
  • $\begingroup$ @Ari, Actually $NPC\not = P$, even if $P=NP$. $\endgroup$
    – Tom van der Zanden
    Commented Nov 28, 2015 at 18:33
  • $\begingroup$ @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. $\endgroup$
    – Ari
    Commented Nov 30, 2015 at 13:37
  • 2
    $\begingroup$ @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. $\endgroup$
    – Tom van der Zanden
    Commented Nov 30, 2015 at 14:14

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • 5
    $\begingroup$ I can't follow your example. The intersection of HORN-SAT and ANTIHORN-SAT is a pretty boring language that is definitely in P. $\endgroup$
    – Yuval Filmus
    Commented Aug 29, 2015 at 9:59
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Aug 29, 2015 at 20:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Aug 29, 2015 at 20:30
  • 4
    $\begingroup$ 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$. $\endgroup$
    – Yuval Filmus
    Commented Aug 30, 2015 at 5:13
  • 3
    $\begingroup$ @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.. $\endgroup$
    – Ari
    Commented Aug 31, 2015 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.