Algorithmic Reduction (Median of medians, quicksort)

Question

I'm trying to better understand reduction, and I'm currently looking at the two algorithms, "Median of medians" and Quicksort.

I understand that both algorithms use a similar (effectively identical) partition subroutine to help solve their problems, which ends up making them quite similar.

Select(A[1...n],k):  // Pseudocode for median of medians
  m = [n/5]
  for i from 1 to m:
    B[i] = Select(A[5i-4..5i],3)
  mom = Select(B[1..m],m/2)

  r = partition(A[1..n],mom)  // THIS IS THE SUBROUTINE

  if k < r:
    return Select(A[1..r-1],k)
  else if k > r:
    return Select(A[r+1..n],k-r)
  else
    return mom

So does the term "reduction" make any sense in regards to these two algorithms? Do any of the following make sense?

• Median of Medians/Quicksort can be reduced to a partition subroutine

• Median of medians reduces to quicksort

• Quicksort reduces to median of medians

Answer 1

This really depends on your definition of "reduction."

The standard type of reduction that's usually discussed is a mapping reduction (also called a many-one reduction). A mapping reduction from problem X to problem Y is the following:

Given an input I_X to problem X, transform it into an input I_Y to problem Y. Then, run a solver for problem Y on I_Y and output that answer.

In a mapping reduction, you get to make exactly one call to a subroutine that solves problem Y and you have to output whatever answer you get back from that subroutine. For example, you can reduce the problem of "is this number even?" to the problem of "is this number odd?" by adding one to the number and outputting whether the resulting number is odd.

As a non-example of a mapping reduction, consider these two problems: first, the problem "is every boolean in this list true?," and second, the problem "is some boolean in this list false?" If you have a solver for the second problem, you can use it to solve the first by running the solver for the second problem and outputting the opposite result: a list of booleans has some element that's false if and only if it's not the case that every element of the list is true. However, this reduction isn't a mapping reduction because we're flipping the result produced by the subroutine.

A different type of reduction that's often used is the Turing reduction. A Turing reduction from problem X to problem Y is the following:

Build an algorithm that solves problem X assuming that there is a magic black box that always solves problem Y.

All mapping reductions are Turing reductions, but not the other way around. The above reduction from "is everything true?" to "is something false" is not a mapping reduction, but it is a Turing reduction because you can use the subroutine for "is something false?" to learn whether or not the list contains any false values, then can output the opposite.

Another major difference between mapping reductions and Turing reductions is that in a Turing reduction, you can make multiple calls to the subroutine that solves problem Y, not just one.

You can think of both quicksort and median-of-medians as algorithms that use partitioning as a subroutine. In quicksort, that subroutine does all the heavy lifting required to sort everything, and in median-of-medians it does one of the essential steps to shrink down the input. Since both algorithms make multiple calls to the subroutine, you can think of them as Turing-style reductions. Quicksort is a reduction from sorting to partitioning, while median-of-medians is a reduction from selection to partitioning.

Hope this helps!

Answer 2

I don't think either can be reduced to the other (in any meaningful way, anyway). You could use the median of medians to choose the pivot for a Quicksort (but nearly nobody actually does). A Quicksort still has to carry out some other steps based on the pivot element though (specifically, partitioning the data based on the pivot).

Likewise, median of medians can't be reduced to Quicksort because a Quicksort does extra work that (among other things) prevents it from meeting the complexity guarantee of the median of medians.