That's another very important reason to
use reductions. and that gets us closer to
our goal of being able to classify the
difficulty of problems, and that's to
establish lower bounds. so let's take a
look at that. So, what we want to do is
come up with a proof that a problem
requires a certain number of computational
steps. and we had an example of that for
sorting. We showed in the de, decision
tree model, any compare based sorting
algorithm has to use at least at least N
log N and compares in the worst case. And
we show that be showing that no matter
what the algorithm is, it has to
distinguish between all the possible cases
of sorting. And that led us to in fact, a
tree that has N factorial leaves on the
bottom. And the height of the tree has got
to be at least log of that, which is N log
N. And you can go back to the sorting
lecture and look at that. now that's a
complicated argument that certainly took
you a little while to understand. and, in
general, it's extremely different,
difficult to establish lower bounds
because it's generally requires a
complicated argument like that. You have
to be arguing about all possible
algorithms and that's very often tough to
do. Initially, there was a lot of optimism
that we would be able to have lower bounds
as researchers worked more and more. And
we'd be able to classify problems. This
actually worked out pretty difficult to
get non-trivial lower bounds for all kinds
of computational problems where people
thought it would be easy. But the good
news is that reduction allows us to take
the ones that we have and spread the lower
bound. so, for, if we can reduce sorting
to a new problem and, without too high a
cost of reduction, that gives us an N log
N lower bound on that problem. So, let's
see how that works. so we have to make
sure the cost of the reduction is not
high, that's key. so, and actually, most
of the time, like in the examples that
we've looked at, we used linear time
reductions. So, that is we only use a
constant number of calls to Y. and we use
just a linea r number of steps, so usually
we're going through everything in the
input and output to do some kind of
conversion, and that's what we've done in
all the examples that we've seen so far.
so, then the idea is, so if there's a
lower bound for X, and you reduce X to Y,
that establishes a lower bound than Y,
right? So why is that? If I could solve
for Y more quickly, then I could use the
reduction to solve X more quickly. so if I
have a reduction from X to Y and there's a
lower bond of N log N and X, I can't have
a linear logarithm on Y. Because if I did
and I have a linear time reduction, that
would give me a linear time algorithm for
X. Same way if I have a lower bound of n
squared for X, I can't have an N login
algorithm for Y. Because if I, if I did,
since I reduced X to Y, then that would
give me linear time algorithm for Y. So,
the reduction allows us to propagate the
lower bound. If I could solve Y, then I
could easily solve X but I know I can't
easily solve X, so therefore I can't
easily solve Y. It's a very powerful
technique and really where most of our
lower bounds comes from. So, just for an
example, let's look at lower bound for the
convex hull algorithm. and it's again,
convex hull certainly don't seem so
related but it's actually the case that in
any algorithm for convex hull is going to
take N log N. And so we start with a more
general statement about sorting. use the
so-called quadratic decision tree model.
and this is just a detail about the model
of computation that makes the idea of
comparing a serving algorithm to a, a
convex hull algorithm. It makes, it makes
them both use the same operation. So quad,
quadratic decision tree you get not just
these comparisons, but you can use tests
like this the, the product of the
difference of two numbers. are they less
than zero or not? and those are the basic
kinds of operations that you're going to
use in the in the geometric algorithms.
And so, the proposition is that under this
model, sorting linear time reduces to
convex hull. so that says, if I can com
pute the convex hull, then I can sort.
since I can't sort faster than N log N, I
can't do convex hull faster than N log N.
and the proof is not terribly difficult
but the implication is really important.
So, convex hull algorithms it was just
based on that idea, am I making the right
turn? that's called a CCW test in
computational geometry. I have three
points, and going from first to second to
third, is that a count, counterclockwise
turn? and then, you can implement that
test with these kind of quadratic things.
It's just testing the slopes of two lines
and comparing them. So, it's kind of like
a comparison. and, and the implication of
the fact that sorting reuses a convex hull
means that you can't solve a convex hull
fast. and so how do we do the reduction
between sorting and convex hull? and
again, the, I have a sorting instance, I
have some numbers to sort. and what I want
to do is create a convex hull instance
that gives me sort. Well, all we do is we
take the numbers that were supposed to be
sorted and we convert them to points on a
parabola. so we just take X1 and X1
squared, and X2 and X2 squared and like
that. Those are points parabola. now,
there's no points and, and we give that to
the convex hull algorithm. Now, all of
those points are on the convex hull. in a
convex hull algorithm, its supposed to
return on in clockwise order. and you can
see with just finding the smallest that
gives us the points in sorted order. So
the convex hull algorithm does its job.
However, it does it we can take the
solution to the convex hull algorithm, and
get a solution to the sorting algorithm.
Sorting reduces the convex hull. therefore
our convex hull can't be easy cuz that
would make sorting easy. this kind of
thinking is really, is really profound and
it has really done a lot to enhance our
understanding of the difficulty of
different algorithmic problems. so,
that's, that's the proof that I just
explained. this parabola thing is
definitely going to be convex and all the
things are on the hull, so we just get the
po int that's got the most negative X
coordinate and you've got the integers in
order. so establishing lower bounds
through reduction is really important. we
have a big convex hull problem to solve
and, and we're wondering, do we have a
linear time algorithm for this? It's a
quite natural thing to wonder. and so how
are you going to convince yourself that
there's no linear time convex hull
algorithm? one thing you can do, and
believe me, a lot of people did this, is
just try to find a linear time algorithm.
Keep working at it, keep working at it.
you're going to use algorithms that are
based on this simple kind of comparison
between points. It doesn't seem like it
should take N log N, it seems like we
should be able to find a linear time
algorithm. and that's the hard way. The
easy way is to know that reduction from
sorting, and that means there's no point
in to try to put in our effort to try to
improve on the Graham scan. Graham scan
gets it done in N log N. We can't do
better than N log N so we might as well
call it a day and move on to some other
problem. and that's an example of
reduction for proving lower bounds to help
us guide our algorithm design efforts.