What will happen if any language in NP ∩ co-NP will become NP-complete?

64 Views Asked by At

I approached this question like this:

Let B ∈ NP ∩ co-NP and B is also NP-complete. Then any other problem in NP can be reduced to B. Now take A ∈ co-NP. Then ~A ∈ NP which can be reduced in polynomial time to B.

I think this will cause NP and co-NP to merge together or NP will become equal to co-NP. But how to proceed that I don't know.

1

There are 1 best solutions below

0
On

Let $B$ be a language in NP and co-NP.
If B is also in NP-Complete then NP = co-NP.

To prove that, we need to prove: $A \in NP \iff A \in$ co-NP

$A \in NP$
$\Rightarrow A <_p B$ $\quad\quad$(since $B \in$ NP-Complete)
$\Rightarrow \bar A <_p \bar B$
$\Rightarrow \bar A \in NP \quad\;\;$ (since the NTM for $\bar B$ is also an NTM for $\bar A$)
$\Rightarrow A \in$ co-NP
which proves $A \in NP \Rightarrow A \in$ co-NP

$A \in$ co-NP
$\Rightarrow \bar A \in NP$
$\Rightarrow \bar A <_p B \quad\quad$ (since $B \in$ NP-Complete)
$\Rightarrow A <_p \bar B \quad\quad$
$\Rightarrow A \in$ NP $\quad\quad$ (since the NTM for $\bar B$ is also an NTM for A)
which proves $A \in$ co-NP $\Rightarrow A \in$ NP