Java Reference
In-Depth Information
There is another use of reductions aside from applying an old algorithm to solve
a new problem (and thereby establishing an upper bound for the new problem).
That is to prove a lower bound on the cost of a new problem by showing that it
could be used as a solution for an old problem with a known lower bound.
Assume we can go the other way and convert SORTING to PAIRING “fast
enough.” What does this say about the minimum cost of PAIRING? We know
from Section 7.9 that the cost of SORTING in the worst and average cases is in
(n log n). In other words, the best possible algorithm for sorting requires at least
n log n time.
Assume that PAIRING could be done in O(n) time. Then, one way to create a
sorting algorithm would be to convert SORTING into PAIRING, run the algorithm
for PAIRING, and finally convert the answer back to the answer for SORTING.
Provided that we can convert SORTING to/from PAIRING “fast enough,” this pro-
cess would yield an O(n) algorithm for sorting! Because this contradicts what we
know about the lower bound for SORTING, and the only flaw in the reasoning is
the initial assumption that PAIRING can be done in O(n) time, we can conclude
that there is no O(n) time algorithm for PAIRING. This reduction process tells us
that PAIRING must be at least as expensive as SORTING and so must itself have a
lower bound in (n log n).
To complete this proof regarding the lower bound for PAIRING, we need now
to find a way to reduce SORTING to PAIRING. This is easily done. Take an in-
stance of SORTING (i.e., an array A of n elements). A second array B is generated
that simply stores i in position i for 0 i < n. Pass the two arrays to PAIRING.
Take the resulting set of pairs, and use the value from the B half of the pair to tell
which position in the sorted array the A half should take; that is, we can now reorder
the records in the A array using the corresponding value in the B array as the sort
key and running a simple (n) Binsort. The conversion of SORTING to PAIRING
can be done in O(n) time, and likewise the conversion of the output of PAIRING
can be converted to the correct output for SORTING in O(n) time. Thus, the cost
of this “sorting algorithm” is dominated by the cost for PAIRING.
Consider any two problems for which a suitable reduction from one to the other
can be found. The first problem takes an arbitrary instance of its input, which we
will call I, and transforms I to a solution, which we will call SLN. The second prob-
lem takes an arbitrary instance of its input, which we will call I
0
, and transforms I
0
to a solution, which we will call SLN
0
. We can define reduction more formally as a
three-step process:
1. Transform an arbitrary instance of the first problem to an instance of the
second problem. In other words, there must be a transformation from any
instance I of the first problem to an instance I
0
of the second problem.
2. Apply an algorithm for the second problem to the instance I
0
, yielding a
solution SLN
0
.
