# Do problems in P only reduce to NP and coNP problems?

Consider the languages $B,C,D$, such that $B\le_p C$ and $B\le_p D$.
Statement: $B\in P, D\in NP, C\in coNP$.

Is the statement true for every $B,C,D$?

I know that the answer is no and I have tried to come up with a conunter-example. I thought about taking $D\in NPC$ or $C \in coNPC$ but that didn't yield anything good.

• this is a case in getting tripped up in abstractions. think about it, can "hard" problems "be reduced" to "less hard" problems? – vzn Jun 22 '15 at 22:57

One short answer, take $B$ be to be any problem in $\mathsf{P}$. The reduction is then powerful enough to simply solve the problem as part of the reduction, and consequently produce a trivial yes or no instance at the other end as appropriate. Then we can take $C$ and $D$ to be anything, they don't even have to be computable.
A more interesting, but conditional answer, is to take $B$, $C$ and $D$ to be any three $\mathsf{NP}$-complete problems (they don't even need to be different ones). Every $\mathsf{NP}$-complete problem is polynomial-time many-one reducible to every other $\mathsf{NP}$-complete problem, so the two reducibility conditions hold trivially. If $\mathsf{P} \neq \mathsf{NP}$, then $B$ can't be in $\mathsf{P}$, and if $\mathsf{NP} \neq co\mathsf{NP}$, then $C$ can't be in $co\mathsf{NP}$. You can do essentially the same thing by taking them all to be $co\mathsf{NP}$-complete. Taking it further, you can do this for any class in the polynomial hierarchy, and the statement being true would imply a collapse to whatever level you chose, another thing that is viewed as unlikely to happen. You could also choose a selection of $\mathsf{PSPACE}$-complete problems, and the statement would imply $\mathsf{P} = \mathsf{PSPACE}$, which also seems unlikely to be true.
• How can $B \in P \cap NPC$? (Isn't it empty?) – Elimination Jun 22 '15 at 14:29
• @Elimination, If $P \neq NP$, then it's empty, if $P = NP$, then $P = NPc$. – Luke Mathieson Jun 23 '15 at 0:41
• Could you give an example of $L\in P\cap NPC$. I can't think of any – Elimination Jun 23 '15 at 7:27
• @Elimination, I can't, if I could then I would have a proof that $P=NP$. It may be true that $P=NP$, in which case $L$ could be any problem in $P$. If it turns out that $P\neq NP$, then there is no such $L$. – Luke Mathieson Jun 24 '15 at 0:11