Is linear-time reduction symmetric?

By reduction I mean the following:

Problem X linear reduces to problem Y if X can be solved with:
a) Linear number of standard computational steps.
b) Constant calls to subroutine for Y.

If a problem X reduces to a problem Y, is the opposite reduction also possible? Say

X = Given an array tell if all elements are distinct
Y = Sort an array using comparison sort

Now, X reduces to Y in linear time i.e. if I can solve Y, I can solve X in linear time. Is the reverse always true? Can I solve Y, given I can solve X? If so, how?

-

migrated from cstheory.stackexchange.comMay 1 '13 at 3:11

This question came from our site for theoretical computer scientists and researchers in related fields.

No, it is not symmetric.

Here's my counter-example: Consider the language $L_1 = \{A:A'| A'$ is $A$ sorted$\}$ and $L_2 = \{A:a| a$ is the largest element in $A\}$.

We can solve the max-element problem with a constant number of calls to a machine solving sorting. Just sort $A$ then take the first element. But we can't solve sorting with a constant number of calls to a machine solving max-element (otherwise, we could sort in $O(n)$, which is known to be impossible).

-