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

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

  • 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