# Reducing from NPC to Co-NPC => NP = Co-NP?

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?

yes

# Proof

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.

• 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? Sep 21, 2019 at 13:42
• 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. Sep 21, 2019 at 13:51
• Can you tell me what polytime reduction closure means? Sep 21, 2019 at 14:10
• "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. 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