0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

In short

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.

$\endgroup$
  • $\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$ – Edmundo Del Gusto Sep 21 '19 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$ – artas Sep 21 '19 at 13:51
  • $\begingroup$ Can you tell me what polytime reduction closure means? $\endgroup$ – Edmundo Del Gusto Sep 21 '19 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$ – artas Sep 21 '19 at 14:17
0
$\begingroup$

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

$\endgroup$

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.