Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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.

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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