Is polynomial time reduction commutative?

519 Views Asked by At

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?

2

There are 2 best solutions below

3
On BEST ANSWER

Isn't it the case that $D_1\le_p D_1$?

0
On

You can get counterexamples by taking $D_1$ and $D_2$ to be any two decision probalems that are both solvable in polynomial time.

Another batch of counterexamples arises by taking any two NP-complete problems.