# Is polynomial time reduction commutative?

True or False: $D_1$ and $D_2$ are decision problems, and $D_1 \leq_p D_2$, then cannot be that $D_2 \leq_p D_1$

I think it is false because we already have a mapping for all yes instance from $D_1$ that are also yes instances in $D_2$, so anything that is not a yes instance from this mapping in $D_2$ is also not a yes instance in $D_1$ and can be determined in polynomial time.

Is this correct?

• I can't understand your reason for thinking it's false, but MJD has indicated a simple proof that it's false. Since you seem to not like that proof (perhaps too easy?), I've added an answer with a lot of other counterexamples. Carl Mummert's comment also provides some easy counterexamples. – Andreas Blass Jul 27 '13 at 0:58

Isn't it the case that $D_1\le_p D_1$?
• Ummm yes. But if $D_1 \neq D_2$ would that still hold? I'm not sure what you mean. – zeion Jul 27 '13 at 0:26
• The question does not say $D_1 \not = D_2$. But for example you can change any one value of $D_1$ and the result will be polynomial-time equivalent to $D_1$. – Carl Mummert Jul 27 '13 at 0:37
• @zeion: You want to decide whether it is true that $D_1\le_p D_2$ implies $\lnot (D_2\le_p D_1)$. If this is false, it is enough to find a single counterexample. Let $D_1$ be any decision problem, and take $D_2$ be the same problem. Then you have both $D_1\le_p D_2$ and $D_2 \le_p D_1$, which falsifies the claim you were asking about. – MJD Jul 27 '13 at 2:29
You can get counterexamples by taking $D_1$ and $D_2$ to be any two decision probalems that are both solvable in polynomial time.