# Tag Info

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