patternMinor
Question on NP $\cap$ coNP
Viewed 0 times
conpcapquestion
Problem
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$
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$
Solution
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:
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.
- A witness for $x \in L_1$ and a witness for $x \notin L_2$; or
- 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.
Context
StackExchange Computer Science Q#42704, answer score: 5
Revisions (0)
No revisions yet.