# Why does SAT-UNSAT $\in NP \implies NP = coNP$

I was reading this post about the DP completeness of the problem SAT-UNSAT (both are well defined in this post). The answer added a note at the end that states the class complexity DP differs from NP, unless NP = coNP.

I fail to see why.

I searched and I came across multiples posts such at this one and that one that prove that if SAT-UNSAT is in coNP, then NP = coNP. But unless the fact that SAT-UNSAT $$\in NP \implies$$ SAT-UNSAT $$\in coNP$$ (which I do not see), then those proofs are not exactly what would help me. The same goes for this question, I would need SAT-UNSAT $$\in coNP$$.

Question : Considering the first question (and the answer associated), if the problem SAT-UNSAT $$\in NP$$, why does NP = coNP.

My take : Well, I can see that the problem SAT-UNSAT is NP-hard and coNP-hard. If SAT-UNSAT $$\in NP$$, then SAT-UNSAT is NP-complete. This implies things such that the problem UNSAT (which is coNP-complete) is NP-hard since we can reduce UNSAT to SAT-UNSAT which is NP-complete. That's all I got and that doesn't really help.

I'd appreciate any clarification on the subject. Thanks to you all

## 1 Answer

Suppose that $$X$$ is a coNP problem which is NP-hard.

Let $$A$$ be any problem in NP. Since $$X$$ is NP-hard, there is a polytime reduction from $$A$$ to $$X$$. Since $$X$$ is in coNP, this shows that $$A$$ is in coNP.

We have shown that $$\mathsf{NP} \subseteq \mathsf{coNP}$$. Now suppose $$B$$ is in coNP. Then $$\overline{B}$$ is in NP, and so in coNP. Hence $$B$$ is in NP. This shows that also $$\mathsf{coNP} \subseteq \mathsf{NP}$$, and so $$\mathsf{NP} = \mathsf{coNP}$$.

• Are you implying that if a problem DP is in NP, then is also is in coNP? Because my question is about SAT-UNSAT (or any DP-complete problem really), and nowhere does it say that it is in coNP. – Exeloz Sep 30 '20 at 13:41
• Let's suppose that a DP-complete problem is in NP, then why is it that the problem is in coNP? – Exeloz Sep 30 '20 at 13:43
• Switch NP and coNP on my answer everywhere. – Yuval Filmus Sep 30 '20 at 14:08
• Well, I could have figured this out on my own really... All this post wasn't really needed after all – Exeloz Sep 30 '20 at 14:12