9
$\begingroup$

I've been thinking about transformations on $NP$-complete problems that produce languages known to be in $P$. However, I can't seem to find an example of two $NP$-complete languages whose union is in $P$. I would imagine that such a pair exists (perhaps something like "every object has exactly one of two properties, but it's $NP$-complete to determine whether any given object has one of those properties"), though I don't know anything of this sort.

Are such pairs of languages known to exist? Or is their existence an open problem?

Thanks!

  • 0
    An $NP$-complete problem and its complement.2012-06-09
  • 8
    @RahulNarain- My understanding is that no complement of an NP-complete language is known to be NP-complete, since this would imply that NP = co-NP, which is currently an open problem. Am I mistaken about this?2012-06-09
  • 0
    My mistake. I'll leave the comment up so nobody else falls for it.2012-06-09

2 Answers 2

13

Take two $NP$-complete languages: $L$, whose alphabet is the lower-case letters $a-z$, and $U$, whose alphabet is the upper-case letters $A-Z$. Now add all upper-case strings to $L$, and all lower-case strings to $U$. The resulting languages are still $NP$-complete, but their union is the set of all strings with constant case, which is certainly in $P$.

  • 1
    Your example is built quite poetically, so I do find it more satisfying :).2012-06-09
  • 2
    Note that unless NP = co-NP, no solution can be of the form "every object has exactly one of two properties $A$ or $B$" suggested by the question: indeed if $A,B$ are disjoint and NP-complete and $A\cup B$ is in P, then $A=(A\cup B)\setminus B$ is in co-NP.2012-06-12
  • 1
    Instead of changing letters, you can adjoin a prefix: $(0L \cup 1X) \cup (1L \cup 0X)$, where $L$ is NP-complete and $X$ is the full language.2012-06-23
  • 0
    +1,interesting.2014-08-03
  • 0
    If such a union is in P then its words can be enumerated in poly time further it can be checked in poly time weather a given word belonged to a given NP language-in effect making it possible to enumerate it in poly time !2015-09-28
  • 0
    Cont.. Above won't be possible for an NP complete problem unless P equalls NP2015-09-28
13

It's true that such pairs exist, but I'm afraid I can only think of trivial unsatisfying examples. Take any two NP-complete languages on disjoint domains and glue them together so that their union is essentially everything.

For instance, take $L_1$ to be the set of all hamiltonian graphs, union the set of all boolean expressions. Then take $L_2$ to be the set of all graphs, together with satisfiable boolean expressions. Then both $L_1$ and $L_2$ are still NP-complete, but $L_1 \cup L_2$ consists of all graphs and all boolean expressions, which is a very boring language and clearly in P (I suppose one could even make it regular).

  • 4
    Our examples are essentially the same (except that I'm satisfied with mine!)2012-06-09
  • 0
    How do we know that the set of all Hamiltonian graphs U set of all boolean expressions is NP complete ?2015-09-28
  • 0
    @ARI Do you already know that HAMILTONIAN is NP-complete? There is an obvious polynomial reduction between that and $L_1$ in both directions.2015-09-28
  • 0
    @ErickWong As I commented to the question above - If L1 U L2 is in P then we can effectively enumerate every word of L1 in Ptime- which won't be possible unless P equalls NP2015-09-28
  • 0
    @ARi Wrong, just think about what the set $L_1 \cup L_2$ actually is (I already described it in my answer). You absolutely do not need to enumerate $L_1$ to enumerate $L_1 \cup L_2$. That you commented the same wrongness previously does not make it any more right.2015-09-29