4

There are at least two ways to do it. The first is to take a disjoint sum of $B$ and $C$, which can be done in many ways, for example $$ \{0x : x \in B\} \cup \{1y : y \in C\}. $$ The second is to use an NP-complete language $L$ as an oracle. Since any problem in NP reduces to $L$ in polynomial time, you can simulate a $B$-oracle using an $L$-oracle.


3

The answer is no, and the reason is that $\mathrm{P}$ is trivially closed under complement. Just by definition of $\mathrm{co}$, it follows that $\mathrm{coNP} = \mathrm{P}$ is equivalent to $\mathrm{NP} = \mathrm{coP}$, and then we use that $\mathrm{coP} = \mathrm{P}$ to conclude that $\mathrm{coNP} = \mathrm{P}$ iff $\mathrm{NP} = \mathrm{P}$.


1

The proof is by induction. Here is the inductive step. Suppose that we know both of the following inequalities: $$ x_1 + \cdots + x_m \leq 1 \\ x_2 + \cdots + x_{m+1} \leq 1 $$ Add them to get $$ x_1 + 2x_2 + \cdots + 2x_m + x_{m+1} \leq 2 $$ Add the axiom $x_1 + x_{m+1} \leq 1$ to get $$ 2x_1 + \cdots + 2x_{m+1} \leq 3 $$ Divide by 2 and round down to get $...


1

Let X be any problem in NP, which means there is a simple proof whenever the answer is YES. Now take the problem X’: “Does X have the answer NO”. That’s in co-NP, so it would be in P, therefore X isin P.


1

If co-$\mathsf{NP} = \mathsf{P}$ then $\mathsf{NP} = \text{co-}\mathsf{P} = \mathsf{P}$.


Only top voted, non community-wiki answers of a minimum length are eligible