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?