# Question on NP $\cap$ coNP

I'm struggling with a past paper question and would appreciate any hints:

Suppose $L_1, L_2 \in$ NP $\cap$ coNP and $L_1 \oplus L_2 = \{ x : x$ is in exactly one of $L_1$ or $L_2 \}$. Then prove that $L_1 \oplus L_2 \in NP \cap coNP$

• What have you tried? Where did you get stuck? We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – D.W. May 18 '15 at 16:12

Hint: What $L \in \mathsf{NP} \cap \mathsf{coNP}$ means is that if $x \in L$ then there is a witness for this, and if $x \notin L$ then there is a witness this. From these witnesses for $L_1,L_2$ you can easily construct witnesses for $L_1 \oplus L_2$. A witness for $x \in L_1 \oplus L_2$ would be:
1. A witness for $x \in L_1$ and a witness for $x \notin L_2$; or
2. A witness for $x \notin L_1$ and a witness for $x \in L_2$.
A witness for $x \notin L_1 \oplus L_2$ is similar and left as an exercise.
More generally, if $L_1,\ldots,L_k \in \mathsf{NP} \cap \mathsf{coNP}$ and $\phi$ is any function on $k$ inputs, then $\phi(L_1,\ldots,L_k) \in \mathsf{NP} \cap \mathsf{coNP}$ (defined analogously to $L_1 \oplus L_2$), for similar reasons.