9

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!

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

2 Answers2

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

Erick Wong
  • 25,198
  • 3
  • 37
  • 91
  • 4
    Our examples are essentially the same (except that I'm satisfied with mine!) – TonyK Jun 09 '12 at 09:42
  • How do we know that the set of all Hamiltonian graphs U set of all boolean expressions is NP complete ? – ARi Sep 28 '15 at 12:52
  • @ARI Do you already know that HAMILTONIAN is NP-complete? There is an obvious polynomial reduction between that and $L_1$ in both directions. – Erick Wong Sep 28 '15 at 16:41
  • @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 NP – ARi Sep 28 '15 at 20:18
  • @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. – Erick Wong Sep 29 '15 at 03:04
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$.

TonyK
  • 64,559
  • 1
    Your example is built quite poetically, so I do find it more satisfying :). – Erick Wong Jun 09 '12 at 17:16
  • 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. – Generic Human Jun 12 '12 at 16:19
  • 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. – sdcvvc Jun 23 '12 at 09:47
  • +1,interesting. – XL _At_Here_There Aug 03 '14 at 20:18
  • 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 ! – ARi Sep 28 '15 at 10:05
  • Cont.. Above won't be possible for an NP complete problem unless P equalls NP – ARi Sep 28 '15 at 12:22