# Two $NP$-complete languages whose union is in $P$?

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!

-
An $NP$-complete problem and its complement. –  Rahul Jun 9 '12 at 8:28
@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? –  templatetypedef Jun 9 '12 at 8:29
My mistake. I'll leave the comment up so nobody else falls for it. –  Rahul Jun 9 '12 at 8:31

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$.

-
Your example is built quite poetically, so I do find it more satisfying :). –  Erick Wong Jun 9 '12 at 17:16
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. –  Generic Human Jun 12 '12 at 16:19
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. –  sdcvvc Jun 23 '12 at 9:47
+1,interesting. –  XL _at_China Aug 3 '14 at 20:18

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).

-
Our examples are essentially the same (except that I'm satisfied with mine!) –  TonyK Jun 9 '12 at 9:42