1
$\begingroup$

Is it true that if $S\in\left(NP\bigcup coNP\right)$ then $\overline{S}\in NP\bigcap coNP$?

I couldn't find any answer to that question.

My attempt at proving it:

If $S\in\left(NP\bigcup coNP\right)$, then, by set theory, $S=A\bigcup B$ for some $A\in NP\wedge B\in coNP$.

Therefore the complement of $S$ is $\overline{S}=\overline{A\bigcup B}=\overline{A}\bigcap\overline{B}\in NP\bigcap coNP$

$\endgroup$
0
$\begingroup$

Your attempt isn't correct.

There is a distinction between $S\in (NP\cup co-NP)$, and $S\in (NP\lor co-NP):=\{A\cup B|A\in NP, B\in co-NP\}$

You assumed both are the same, however the first talks about $S$ being in either $NP$ or $co-NP$, while the second talks about $S$ being a union of something from $NP$ and something else from $co-NP$.


About the question in title, we actually don't know. If $NP\neq co-NP$, then there is some $L\in NP\setminus co-NP$ (or the other way around), which means that $L\in (NP\cup co-NP)$ but $\overline{L}\notin (NP\cap co-NP)$ (since $L\notin NP$ then $\overline{L}\notin co-NP$)

But if $NP=co-NP$, then clearly what you stated would be trivially true.

So essentially, what you tried to prove is equivalent to the open problem "Is $NP=co-NP$ or not?".

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