HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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 ..."?

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

Context

StackExchange Computer Science Q#52305, answer score: 2

Revisions (0)

No revisions yet.