# 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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8211736083030701, "perplexity": 209.6294812971657}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2019-39/segments/1568514573289.83/warc/CC-MAIN-20190918131429-20190918153429-00356.warc.gz"}