1
$\begingroup$

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.

$\endgroup$
1
  • 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, 2015 at 22:57

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ How can $B \in P \cap NPC$? (Isn't it empty?) $\endgroup$ Jun 22, 2015 at 14:29
  • 1
    $\begingroup$ @Elimination, If $P \neq NP$, then it's empty, if $P = NP$, then $P = NPc$. $\endgroup$ Jun 23, 2015 at 0:41
  • $\begingroup$ Could you give an example of $L\in P\cap NPC$. I can't think of any $\endgroup$ Jun 23, 2015 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$ Jun 24, 2015 at 0:11
  • 1
    $\begingroup$ @Elimination, no problem, we all talk nonsense from time to time - it even turns out to be useful ;) $\endgroup$ Jun 24, 2015 at 11:52

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.