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.