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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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, 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
    Sep 21, 2019 at 13:51
  • $\begingroup$ Can you tell me what polytime reduction closure means? $\endgroup$
    – Edmundo Del Gusto
    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
    Sep 21, 2019 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

Improve this answer
$\endgroup$

Your Answer

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

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