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$

1 Answer 1

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
    Commented Sep 30, 2020 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
    Commented Sep 30, 2020 at 13:43
  • $\begingroup$ Switch NP and coNP on my answer everywhere. $\endgroup$ Commented Sep 30, 2020 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
    Commented Sep 30, 2020 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.