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?


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

  • 1
    $\begingroup$ Your example is built quite poetically, so I do find it more satisfying :). $\endgroup$ – Erick Wong Jun 9 '12 at 17:16
  • 2
    $\begingroup$ 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. $\endgroup$ – Generic Human Jun 12 '12 at 16:19
  • 1
    $\begingroup$ 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. $\endgroup$ – sdcvvc Jun 23 '12 at 9:47
  • $\begingroup$ +1,interesting. $\endgroup$ – XL _At_Here_There Aug 3 '14 at 20:18
  • $\begingroup$ 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 ! $\endgroup$ – ARi Sep 28 '15 at 10:05

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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