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?

  • $\begingroup$ 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. $\endgroup$ – Andreas Blass Jul 27 '13 at 0:58

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

  • $\begingroup$ Ummm yes. But if $D_1 \neq D_2$ would that still hold? I'm not sure what you mean. $\endgroup$ – zeion Jul 27 '13 at 0:26
  • $\begingroup$ 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$. $\endgroup$ – Carl Mummert Jul 27 '13 at 0:37
  • $\begingroup$ @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. $\endgroup$ – 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.

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


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.