patternMinor
Proving that if A⊕B ∈ NP then NP = coNP
Viewed 0 times
provingthatthenconp
Problem
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 ..."?
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 ..."?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#52305, answer score: 2
Revisions (0)
No revisions yet.