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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have this problem,

Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like:

$L_1 \oplus L_2 = \{x | x$ is in exactly one of $L_1, L_2\}$

I do not have a clue how to show it. We know that $L_1 \cap L_2 \in NP$ is unknown. So for that reason it is reasonable to ask only that instance of the problem. From my point of view, if $L_1 \in NP$ there is some verifier for that language which runs in polynomial time. We have such verifier for the second language $L_2$ too. My proposal of the machine M which decides $L_1 \oplus L_2$ is as follows:

Let's have

M = "for the input x:
1. copy x on the second tape
2. run x on M_1 on the first tape
3. if M_1 accepts, (otherwise go to 4.)
    3a) run x on M_2
    3b) if  M_2 accepts, M rejects 
4. run x on M_2, if M_2 accepts, M accepts, otherwise M rejects.

I do not know the relation of this with the co-NP class ... Is my reasoning right? This machine works like a charm for languages $L_1,L_2 \in P$. Does it hold also for that intersection?

Thank you a lot

share|cite|improve this question

We know $L_1,L_2,\overline{L_1},\overline{L_2} \in NP$. To show that the symmetric difference of $L_1$ and $L_2$ lies in $NP \cap coNP$, we need to find two verifiers, one for $L_1 \otimes L_2$ and one for $\overline{L_1 \otimes L_2}$. A certificate that some input $x$ is in $L_1 \otimes L_2$ must guarantee that $x \in L_2, x \notin L_2$ or $x \in L_2, x \notin L_1$. So a machine to verify such a certificate can be built out of the verifiers we know exist for $L_1,L_2$ and their complements. A similar construction will work for $\overline{L_1 \otimes L_2}$.

share|cite|improve this answer
Isn't there a typo? you wrote $x \in L_2, x \notin L_2$, shouldn't be that first $L_2$ $L_1$ instead? – Stefan.M Mar 21 '12 at 0:34
If I have some certificate $w$ for which the verifier V verifies in polynomial time if $x$ is in $L_1$, then if the answer is true, I put this certificate on the verifier for the L_2 and this has to be false? – Stefan.M Mar 21 '12 at 0:41

Your Answer


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.