Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
An $NP$-complete problem and its complement. –  Rahul Jun 9 '12 at 8: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 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

2 Answers 2

up vote 14 down vote accepted

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

share|improve this answer
1  
Your example is built quite poetically, so I do find it more satisfying :). –  Erick Wong Jun 9 '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 9:47
    
+1,interesting. –  XL _at_China Aug 3 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).

share|improve this answer
4  
Our examples are essentially the same (except that I'm satisfied with mine!) –  TonyK Jun 9 '12 at 9:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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