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?
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).