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.

  • 1
    $\begingroup$ this is a case in getting tripped up in abstractions. think about it, can "hard" problems "be reduced" to "less hard" problems? $\endgroup$ – 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.

  • $\begingroup$ How can $B \in P \cap NPC$? (Isn't it empty?) $\endgroup$ – Elimination Jun 22 '15 at 14:29
  • 1
    $\begingroup$ @Elimination, If $P \neq NP$, then it's empty, if $P = NP$, then $P = NPc$. $\endgroup$ – Luke Mathieson Jun 23 '15 at 0:41
  • $\begingroup$ Could you give an example of $L\in P\cap NPC$. I can't think of any $\endgroup$ – Elimination Jun 23 '15 at 7:27
  • 1
    $\begingroup$ @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$. $\endgroup$ – Luke Mathieson Jun 24 '15 at 0:11
  • $\begingroup$ Oh right. That was non-sense to ask it $\endgroup$ – Elimination Jun 24 '15 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.