5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Your chances of getting an answer to this question might be higher on cstheory.stackexchange.com $\endgroup$
    – j.p.
    Mar 21, 2012 at 14:45

2 Answers 2

6
$\begingroup$

Yes, the class NP $\cap$ coNP is closed under symmetric difference. To see this, suppose that $A$ and $B$ are both in NP $\cap$ coNP. This means that the truth of $a\in A$ can be verified in polynomial time with a suitable witness, and also $a\notin A$ can be verified in polynomial time with a suitable witness, and the same for $B$. Let $A\triangle B=(A-B)\cup (B-A)$ be the symmetric difference (the same as what you call $A\oplus B$), and argue as follows:

  • $A\mathrel{\triangle} B$ is in NP. This is because we can verify whether $a\in A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\notin B$ or that $a\notin A$ and $a\in B$. That is, the objects $a$ in the symmetric difference $A\mathrel{\triangle} B$ are verified by a pair of witnesses, which either verify membership in $A$ and not in $B$ or in $B$ but not in $A$.

  • $A\mathrel{\triangle} B$ is in coNP. This is because we can verfiy whether $a\notin A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\in B$ or that $a\notin A$ and $a\notin B$.

So the symmetric difference is in NP $\cap$ coNP, as desired.

(Meanwhile, your proposed algorithm, if interpreted as a nondeterminisitic algorithm, is not correct, since failure to verify membership nondeterministically is not the same thing as a verfication of non-membership. In short, your algorithm can be fooled in the following way: suppose $x$ is in both languages, but in step 2 of your algorithm, $M_1$ happens to choose a branch of computation that doesn't verify membership---an inadequate witness, so it doesn't accept on that branch---but then $M_2$ does accept $x$ in step 4. In this case, you will accept $x$ when you shouldn't.)

$\endgroup$
2
  • $\begingroup$ Yes, you are right that my algorithm is wrong, it works only for languages which are both in P. Since P is in NP \cap coNP I thought that way is good but there are some catches. But the truth is there has to be completely another approach throught verifiers and certificates, that's quite obvious. Thank you once again for your explanation. $\endgroup$
    – Stefan.M
    Mar 21, 2012 at 21:33
  • $\begingroup$ It was my pleasure. I like the question very much, and I think it is a great example to illustrate the point that failing to verify membership is not the same as verifying non-membership. $\endgroup$ Mar 21, 2012 at 22:05
3
$\begingroup$

NP is closed under (finite) unions and intersections, therefore using De Morgan laws, $\mathrm{NP}\cap\mathrm{coNP}$ is closed under unions and intersections. Since it is also trivially closed under complement, it is closed under all Boolean operations, including the symmetric difference.

A more careful argument shows that $\mathrm{NP}\cap\mathrm{coNP}$ is even closed under polynomial-time Turing reductions. (Note that symmetric difference can be computed by an essentially constant-time algorithm querying oracles for the two languages.) In fact, $(\mathrm{NP}\cap\mathrm{coNP})^{\mathrm{NP}\cap\mathrm{coNP}}=\mathrm{NP}\cap\mathrm{coNP}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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