Return to Answer

Yes, the class NP $\cap$ coNP is closed under symmetric difference. To see this, suppose that $A$ and $B$ are both in NP $\cap$ coNP. This means that the truth of $a\in A$ can be verified in polynomial time with a suitable witness, and also $a\notin A$ can be verified in polynomial time with a suitable witness, and the same for $B$. Let $A\triangle B=(A-B)\cup (B-A)$ be the symmetric difference (the same as what you call $A\oplus B$), and argue as follows:

• $A\mathrel{\triangle} B$ is in NP. This is because we can verify whether $x\in A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\notin B$ or that $A\notin A$ and $a\in B$. That is, the objects $a$ in the symmetric difference $A\mathrel{\triangle} B$ are verified by a pair of witnesses, which either verify membership in $A$ and not in $B$ or in $B$ but not in $A$.

• $A\mathrel{\triangle} B$ is in coNP. This is because we can verfiy whether $a\notin A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\in B$ or that $a\notin A$ and $a\notin B$.

So the symmetric difference is in NP $\cap$ coNP, as desired.

(Meanwhile, your proposed algorithm, if interpreted as a nondeterminisitic algorithm, is not correct, since failure to verify membership nondeterministically is not the same thing as a verfication of non-membership. In short, your algorithm can be fooled in the following way: suppose $x$ is in both languages, but in step 2 of your algorithm, $M_1$ happens to choose a branch of computation that doesn't verify membership---an inadequate witness, so it doesn't accept on that branch---but then $M_2$ does accept $x$ in step 4. In this case, you will accept $x$ when you shouldn't.)

Yes, the class NP $\cap$ coNP is closed under symmetric difference. To see this, suppose that $A$ and $B$ are both in NP $\cap$ coNP. This means that the truth of $a\in A$ can be verified in polynomial time with a suitable witness, and also $a\notin A$ can be verified in polynomial time with a suitable witness, and the same for $B$. Let $A\triangle B=(A-B)\cup (B-A)$ be the symmetric difference (the same as what you call $A\oplus B$), and argue as follows:

• $A\mathrel{\triangle} B$ is in NP. This is because we can verify whether $a\in A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\notin B$ or that $a\notin A$ and $a\in B$. That is, the objects $a$ in the symmetric difference $A\mathrel{\triangle} B$ are verified by a pair of witnesses, which either verify membership in $A$ and not in $B$ or in $B$ but not in $A$.

• $A\mathrel{\triangle} B$ is in coNP. This is because we can verfiy whether $a\notin A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\in B$ or that $a\notin A$ and $a\notin B$.

So the symmetric difference is in NP $\cap$ coNP, as desired.

(Meanwhile, your proposed algorithm, if interpreted as a nondeterminisitic algorithm, is not correct, since failure to verify membership nondeterministically is not the same thing as a verfication of non-membership. In short, your algorithm can be fooled in the following way: suppose $x$ is in both languages, but in step 2 of your algorithm, $M_1$ happens to choose a branch of computation that doesn't verify membership---an inadequate witness, so it doesn't accept on that branch---but then $M_2$ does accept $x$ in step 4. In this case, you will accept $x$ when you shouldn't.)

Yes, the class NP $\cap$ coNP is closed under symmetric difference. To see this, suppose that $A$ and $B$ are both in NP $\cap$ coNP. This means that the truth of $a\in A$ can be verified in polynomial time with a suitable witness, and also $a\notin A$ can be verified in polynomial time with a suitable witness, and the same for $B$. Let $A\triangle B=(A-B)\cup (B-A)$ be the symmetric difference (the same as what you call $A\oplus B$), and argue as follows:

• $A\mathrel{\triangle} B$ is in NP. This is because we can verify whether $x\in A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\notin B$ or that $A\notin A$ and $a\in B$. That is, the objects $a$ in the symmetric difference $A\mathrel{\triangle} B$ are verified by a pair of witnesses, which either verify membership in $A$ and not in $B$ or in $B$ but not in $A$.

• $A\mathrel{\triangle} B$ is in coNP. This is because we can verfiy whether $a\notin A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\in B$ or that $a\notin A$ and $a\notin B$.

So the symmetric difference is in NP $\cap$ coNP, as desired.

(Meanwhile, your proposed algorith, if interpreted as a nondeterminisitic algorithm, is not correct, since failure to verify membership nondeterministically is not the same thing as a verfication of non-membership. So your algorithm will be fooled. For example, if $x$ is in both, but in step 2 of your algorithm, $M_1$ chooses a branch of computation that doesn't accept, but then $M_2$ does $x$ in step 4, then you will accept $x$ when you shouldn't.)

Yes, the class NP $\cap$ coNP is closed under symmetric difference. To see this, suppose that $A$ and $B$ are both in NP $\cap$ coNP. This means that the truth of $a\in A$ can be verified in polynomial time with a suitable witness, and also $a\notin A$ can be verified in polynomial time with a suitable witness, and the same for $B$. Let $A\triangle B=(A-B)\cup (B-A)$ be the symmetric difference (the same as what you call $A\oplus B$), and argue as follows:

• $A\mathrel{\triangle} B$ is in NP. This is because we can verify whether $x\in A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\notin B$ or that $A\notin A$ and $a\in B$. That is, the objects $a$ in the symmetric difference $A\mathrel{\triangle} B$ are verified by a pair of witnesses, which either verify membership in $A$ and not in $B$ or in $B$ but not in $A$.

• $A\mathrel{\triangle} B$ is in coNP. This is because we can verfiy whether $a\notin A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\in B$ or that $a\notin A$ and $a\notin B$.

So the symmetric difference is in NP $\cap$ coNP, as desired.

(Meanwhile, your proposed algorithm, if interpreted as a nondeterminisitic algorithm, is not correct, since failure to verify membership nondeterministically is not the same thing as a verfication of non-membership. In short, your algorithm can be fooled in the following way: suppose $x$ is in both languages, but in step 2 of your algorithm, $M_1$ happens to choose a branch of computation that doesn't verify membership---an inadequate witness, so it doesn't accept on that branch---but then $M_2$ does accept $x$ in step 4. In this case, you will accept $x$ when you shouldn't.)

Yes, the class NP $\cap$ coNP is closed under symmetric difference. To see this, suppose that $A$ and $B$ are both in NP $\cap$ coNP. This means that the truth of $a\in A$ can be verified in polynomial time with a suitable witness, and also $a\notin A$ can be verified in polynomial time with a suitable witness, and the same for $B$. Let $A\triangle B=(A-B)\cup (B-A)$ be the symmetric difference (the same as what you call $A\oplus B$), and argue as follows:

• $A\mathrel{\triangle} B$ is in NP. This is because we can verify whether $x\in A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\notin B$ or that $A\notin A$ and $a\in B$. That is, the objects $a$ in the symmetric difference $A\mathrel{\triangle} B$ are verified by a pair of witnesses, which either verify membership in $A$ and not in $B$ or in $B$ but not in $A$.

• $A\mathrel{\triangle} B$ is in coNP. This is because we can verfiy whether $a\notin A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\in B$ or that $a\notin A$ and $a\notin B$.

So the symmetric difference is in NP $\cap$ coNP, as desired.

(Meanwhile, your proposed algorith, if interpreted as a nondeterminisitic algorithm, is not correct, since failure to verify membership nondeterministically is not the same thing as a verfication of non-membership. So your algorithm will be fooled.)

Yes, the class NP $\cap$ coNP is closed under symmetric difference. To see this, suppose that $A$ and $B$ are both in NP $\cap$ coNP. This means that the truth of $a\in A$ can be verified in polynomial time with a suitable witness, and also $a\notin A$ can be verified in polynomial time with a suitable witness, and the same for $B$. Let $A\triangle B=(A-B)\cup (B-A)$ be the symmetric difference (the same as what you call $A\oplus B$), and argue as follows:

• $A\mathrel{\triangle} B$ is in NP. This is because we can verify whether $x\in A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\notin B$ or that $A\notin A$ and $a\in B$. That is, the objects $a$ in the symmetric difference $A\mathrel{\triangle} B$ are verified by a pair of witnesses, which either verify membership in $A$ and not in $B$ or in $B$ but not in $A$.

• $A\mathrel{\triangle} B$ is in coNP. This is because we can verfiy whether $a\notin A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\in B$ or that $a\notin A$ and $a\notin B$.

So the symmetric difference is in NP $\cap$ coNP, as desired.

(Meanwhile, your proposed algorith, if interpreted as a nondeterminisitic algorithm, is not correct, since failure to verify membership nondeterministically is not the same thing as a verfication of non-membership. So your algorithm will be fooled. For example, if $x$ is in both, but in step 2 of your algorithm, $M_1$ chooses a branch of computation that doesn't accept, but then $M_2$ does $x$ in step 4, then you will accept $x$ when you shouldn't.)