Now, if we put the last two sections together it gives us a way to start to
think about how to classify problems according to their difficulty. Let's look
at how that works. so what we're always looking for is a problem that where the
algorithm matches the, the, lower bound. and so, one way to do that is just use
reduction. so, in order to, we want to prove that two problems X and Y, have the
same complexity or the same research requirements. First, we show that X linear
time reduces to Y. And then we show that Y linear time reduces to X. and then with
that way, even if we don't know what the complexity is at all, we know that X and Y
are, have the same computational requirements. And this is what we just did
for sorting in convex hull. In this case, we know that both of them take time
proportional to N log N but the reducing one to the other in both directions shows
us their, their equivalent with respect to computational requirements. in the one
case reducing sorting to convex hull gave us a lower bound. In the other case,
reducing convex hull to sorting gave us a useful algorithm. but together they're
useful because it helps classify those problems. now, there is a bit of a caveat
to this and this is a little bit of an idealized situation. But it actually is,
is something that can lead to trouble in the real world. So, we have these two
problems. and we have the, these two propositions, that they, in linear time,
reduce to one another. now, it could be that in a big software engineering effort
there there's a lot of people making decisions. and well, so we found out they
have the same complexity. But maybe some system designer has a big project and
there's a lot, a lot of things, so they need both sort and convex hull. And one
programmer is charged with a job of implementing sort. and understands that
well, you could do that using convex hull. I learned this cool trick. And the other
one knows the Graham scan, says, okay, I'm going to index convex hull using sort. and
that's in a big system. and that's going to lead to a problem. It's an infinite
reduction loop which certainly is going to lead to problems. whose fault, well that
would be the boss. Alice and Bob just did what they were suppose to. and it's, they
were all, somebody could argue Alice maybe could have used a library routine for the
sort but you, you get the point for a complex situation. this definitely could
have come up just to show the power of this kind of technique and how it relates
to research that's still ongoing in Computer Science. let's look at some
simple examples from Arithmetic. So here's the grade school integer nullification.
let's do it with bits. So, I have two N bit integers I want to compute the
product. and this is the way you learned to do it in grade school. For every bit in
the bottom you multiply it by the top and then you add them all together. and that's
going to take time proportional to N^2. You have N bits and you have N rows. and
so that's time proportional to N^2. And but now, nowadays, people are doing
integer multiplication on huge integers because mathematical properties of
integers play an important role in cartography and other applications. so,
people are interested in algorithms that are faster than quadratic for something
like integer multiplication. now one, one thing that you can do, first you can do
with reduction is people have figured out that you can take integer division or
square or square root and all different other integer operations and reduce them
to integer multiplication. So, you can show that all of these and, and vice
versa. And so, you can show that all of these things have the same complexity,
even though we all know what it is just by simple reductions one to the other. so and
you can imagine how to do divide to multiply and so forth. These have been
done in all different directions. so now, the question is that so now, they're all
the same difficulty as the Brute force algorithm and how hard is the Brute force
algorithm. well, people have studied that for a long time and actually one of the,
the earliest divide and conquer algorithm by Karatsuba and Ofman showed that the
integer multiplication could be done in time into the 1.585. and it was divide and
conquer, we divide the integers in half and then find a clever way to combine it
to reduce the exponents. And people have been working on this. you can see through
the decades, actually, there's a big breakthrough just in 2007 that is going to
get much closer to N log N. Although there's no known lower bound for this
problem could be linear. And some people are still going to work on it. so, and all
these different algorithms, they get more complicated and may be, you know, useful
for very large N or for different ranges of N. and actually in practice there's the
Multi Precision Library that's used in many symbolic mathematics packages has one
of five different algorithms that it uses for integer multiplication, depending on
the size of the operands. And, and again, in applications such as cryptography the N
can be truly huge. And people want to do this computation. so we don't know what
the difficulty of integer multiplication is, we just know that all the integer
operations are described by this one thing. And it's similar for a matrix
multiplication. one of the, another famous problem that people are still trying to
understand. and again, the secondary school algorithm to compute the entry in
row I and column J, you compute the dot product of the Ith row of one argument,
and the Jth column of the other and the dot product of that, that fills that
entry, and you do that for every entry, so that's going to be time proportional to N
cube, because you have to do N multiplications for each of the N^2
entries in the result matrix. and again there's all different kinds of matrix
operations that can be proven to be equivalent in difficulty to the matrix
multiplication through reduction. and so, that's the you know, of called matrix
multiplication as all these other things like solving systems of linear equations
and determine and, and other things. bu t how difficult is it to multiply two
matrices. So again, reduction gives us a big class of problems to make it even more
interesting to know the difficulty of this one problem. and then, research on the
difficulty of this one problem has been ongoing. in this case running time is N
cube for the brute force algorithm and who knows when that was discovered I don't
know, eighteenth century or fifteenth or something. and then but, when, once
computers got involved the Strassen's famous divide and conquer algorithm like
you know, integer multiplication breaks it down through divide and conquer and gets
the exponent down to 2.808. And people have been working through the years to
find successive improvements to this. The last one went from 2.3737 to 2.3727 which
doesn't seem like much, but maybe one of these research results will be a
breakthrough that will give us an efficient new algorithm for all of these
problems involving matrices. so again, it's very useful to have classified all
these problems and make the even increase the leverage of the research even more.
So, when we started this lecture we started with the idea that it would be
good to classify problems. but it's, it's tough to actually classify them because
there's new research involved, even for things as simple as integer or matrix
multiplication but at least what we can do is put the defined complexity classes.
even though we don't want to know what it is, we know there's a lot of important
problems that have that same complexity. and there's a really important one that
we're going to talk about in the last lecture, called the NP-complete problems,
and all kinds of important problems that fall into that but as the time wears on,
researchers have found ways to put many, many problems into, into, into equivalence
classes. so, at least we know that there's those problems are have the same
difficulty even, even if we don't know what it is. this is actually called the,
the complexity zoo there's really a large number of complexity classes. now a lot of
these are de finitely theoretical devices that are only important in filling in our
understanding of some, some important part of the theory. but many of them like, like
matrix multiplication, integer multiplication, are very important to
practical algorithms. So there's certainly a huge amount of research, I guess, still
going on into trying to understand computational difficulty of the problems.
So, in summary, we use reductions to design algorithms, to establish lower
bounds, and to help us classify problems. but in practice, we've been using them
already. we, we designed algorithms that made use of priority queues in effective
ways. That's a reduction and lots of algorithms for sorting, and really that's
the idea of reusable software modules. We find, you know, fundamental problems, and
we develop implementations that can be used by clients. Every client using an
implementation is doing a reduction. and the other thing is that reductions help us
determine the difficulty of our problem and guide our search towards finding
efficient solution for it. so in particular, when we get to extremely
difficult problems, we'll know whether or not we should look for an exact algorithm
or we should find something that doesn't quite solve the problem. And we'll talk a
lot more about that in the last lecture. And then all of these studies, in the
complexity zoo and in any algorithm that we're going to develop for a complicated
problem, what we're going to want is reduction to link the new problem to
problems that we know how to solve.