In my lecture we learned:

If X is NPC and X in Co-NP => NP = Co-NP

Would it be enough to prove NP = Co-NP if I reduce a problem just in one direction (from NPC to Co-NPC) in polynomial time?

Or would it be necessary to show this for both directions?


2 Answers 2


In short



Let's assume $X$ is NP-complete and $X$ is in co-NP.

We show that $NP \subseteq coNP$ and viceversa.

[$NP\subseteq coNP$]

Because $X$ is NP-complete $=>$ for each $L\in NP$ we can found a polytime function $f$ that $s\in L$ iff $f(s)\in X$.

But $X$ is in coNP $=>$ for the polityme reduction closure of coNP, $L\in coNP$ too $=>$ $NP\subseteq coNP$

[ $coNP \subseteq NP$ ]

let $B\in coNP$ $=>$ $B^c \in NP$ $=>$ $s\in B^c$iff $f(s)\in X$ $=>$ $s\in B$ iff $f(s) \notin X$ $=>$ $s\in B$ iff $f(s) \in X^c$

but because $X \in coNP$ $=> X^c \in NP$ and for polityme reduction closure of $NP$ $=> B \in NP$ $=>coNP\subseteq NP$

So $NP=coNP$ under this assumptions.

  • $\begingroup$ So is it right you can assume that X (NPC) is also in co-NP if there exists a reduction to a Co-NP-complete problem? $\endgroup$ Commented Sep 21, 2019 at 13:42
  • 1
    $\begingroup$ yes, if $X$ reduce to $Y$ and $Y\in coNP$ for the polytime reduction closure of coNP $X\in coNP$. So this is true even more so if $Y$ is coNP-complete. $\endgroup$
    – user89276
    Commented Sep 21, 2019 at 13:51
  • $\begingroup$ Can you tell me what polytime reduction closure means? $\endgroup$ Commented Sep 21, 2019 at 14:10
  • 1
    $\begingroup$ "We say class X is closed under polynomial reductions if $(L_1 ≤_p L_2$ and $L_2\in X)$ $=> L_1\in X$" where $L_1 ≤_p L_2$ mean that there is a polynomial time reduction from $L_1$ to $L_2$. So it's possible to show that P,NP and coNP (and some other classes) are closed under polynomial reductions. $\endgroup$
    – user89276
    Commented Sep 21, 2019 at 14:17

Ok I think I got it know.

If I could reduce a NP-complete problem to a coNP-complete problem every problem in NP can be reduced to every coNP-complete problem and it would show that NP is a subset of coNP.

Because every problem A in coNP has a complement co_A in NP

A in coNP => co_A in NP => co_A in coNP => A in NP

=> every Problem in coNP is in NP

=> NP = coNP

If there is a NPC problem that can be reduced to coNPC => NP = coNP

Edit: I wrote this while the other answer was given


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.