2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Exeloz Sep 30 '20 at 13:41
  • $\begingroup$ Let's suppose that a DP-complete problem is in NP, then why is it that the problem is in coNP? $\endgroup$ – Exeloz Sep 30 '20 at 13:43
  • $\begingroup$ Switch NP and coNP on my answer everywhere. $\endgroup$ – Yuval Filmus Sep 30 '20 at 14:08
  • $\begingroup$ Well, I could have figured this out on my own really... All this post wasn't really needed after all $\endgroup$ – Exeloz Sep 30 '20 at 14:12

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.