# Proving that if A⊕B ∈ NP then NP = coNP

I got this question:

Let $A \oplus B = (A\cap \bar{B})\cup(\bar{A}\cap B)$.

Proof that $NP = coNP$ if and only if $A,B\in NP$ and $A \oplus B\in NP$.

But I don't know how to proof the direction that if $A,B\in NP$ and $A \oplus B\in NP$ then $NP = coNP$.

I have tried to build the non-deterministic machines for $\bar{A}$ and $\bar B$, but I don't know how.

What that I tried: Say I want to build the non-deterministic machine for $\bar{A}$. I know that if $w\in A \oplus B$ and $w\in B$, then for sure $w \in \bar A$. My problem is with the condition if $w\notin A \oplus B$ and $w\notin B$ then $w \in \bar A$, because I don't know if $w\notin A \oplus B$ and $w\notin B$ since I don't know that $NP = coNP$.

So how can I show non deterministic machines for $\bar{A}$ and $\bar B$ when I don't know how to decide if "word is not in ..."?

• Hint: it's clear that NP is closed under intersection (proof?). The task is to show that NP being closed under symmetric difference is equivalent to it being closed under complementation. – G. Bach Jan 26 '16 at 10:07
• @G.Bach I know that NP is closed under intersection. I don't know how it can help me to solve the problem... – nrofis Jan 26 '16 at 10:37
• Further hint: $A \oplus \Sigma^* = \bar{A}$. – Yuval Filmus Jan 26 '16 at 11:00
• Thank you! Didn't think about using specific $B$. Now it's easy :) – nrofis Jan 26 '16 at 11:04
• Can you answer your own question now? – Yuval Filmus Jan 26 '16 at 12:09

If every $A, B \in NP$ and $A \oplus B \in NP$, then let $E$ to be some language $E\in NP$. Since $\Sigma^*\in NP$ then $E \oplus \Sigma^* \in NP$. But $E \oplus \Sigma^* = \bar E$, so $\bar E \in NP$, and we got that $NP \subseteq coNP$.
Let $D$ to be some language $D\in coNP$ ($\bar D \in NP$). Since $\Sigma^*\in NP$ then $\bar D \oplus \Sigma^* \in NP$. But $\bar D \oplus \Sigma^* = D$, so $\bar D \in NP$, and we got that $coNP \subseteq NP$.
And then $NP = coNP$.