Problem Detail: 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?
Asked By : Bruce
Answered By : jmite
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).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11687
