3
$\begingroup$

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 ..."?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – G. Bach Jan 26 '16 at 10:07
  • $\begingroup$ @G.Bach I know that NP is closed under intersection. I don't know how it can help me to solve the problem... $\endgroup$ – nrofis Jan 26 '16 at 10:37
  • 2
    $\begingroup$ Further hint: $A \oplus \Sigma^* = \bar{A}$. $\endgroup$ – Yuval Filmus Jan 26 '16 at 11:00
  • $\begingroup$ Thank you! Didn't think about using specific $B$. Now it's easy :) $\endgroup$ – nrofis Jan 26 '16 at 11:04
  • 1
    $\begingroup$ Can you answer your own question now? $\endgroup$ – Yuval Filmus Jan 26 '16 at 12:09
2
$\begingroup$

Thanks to G. Bach and Yuval Filmus.

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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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