# 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. 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... Jan 26 '16 at 10:37
• Further hint: $A \oplus \Sigma^* = \bar{A}$. Jan 26 '16 at 11:00
• Thank you! Didn't think about using specific $B$. Now it's easy :) Jan 26 '16 at 11:04
• Can you answer your own question now? 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$.