Okay, so next we'll look at what the idea of the classes P and NP mean in terms of
actual problems we're looking at solving. we want to classify our problems the same
way as which scientists classify elements. And the key technique they're going to,
that we're gonna use is reduction. So the problem that we're gonna start with. That
is, the key to this theory is the Boolean satisfiability problem. and we talked
about at the beginning, it's not that different than Gaussian than systems
linear equations. It's just that everything has to be Boolean variables.
and so. given a system of boolean equations, find a solution. and. Even on
it's own, it's a very significant problem. it Has come, it comes up, and, and people
solve huge and, and face huge satisfiability problems in trying to
understand whether trying to prove whether software, to verify software, that
software works correctly. Also, hardware for design automation. people model what's
going on with huge satisfiability problems and solve them. it's, it's so basic that
it even arises in, in, in physics, and scientific studies, and. The so-called,
mean field diluted spin class model. It's a very fundamental, problem that is just,
about, logical reasoning about what's going on, in, in some complex system. now
the question is, so it's a search problem. we know that and what that means is that
if we have a solution, we can efficiently check that we have a solution But the
question is, is it in P? Can we find an algorithm that guarantees to find a
solution in polynomial time? Now people solve huge problems be, but in some sense
maybe they're lucky because the instances that they're trying to solve don't cause
the algorithm to run in polynomial time. But the real question is can we guarantee
that we'll get that in polynomial time? So, well. What do we do? Well. For satisfy
ability, as I mentioned, it's pretty easy to use. Exhaustive search, just try all
the truth assignments. and really what that means is, they have an algorithm that
if doesn't find the right tru th assignment it might wind up trying all of
them. but you might find on earlier and that's, that's what happens with practice.
but the big question is, can we do anything that is really substantially more
clever than sat? then, then the brute force algorithm. that, that is an
algorithm run brute force in the, in the worst, worst case. That's a, that's a
pretty stringent definition of substantially. but that's the one that
we're that we're talking about. can we get less than exponential, worst case
performance. And some people have worked on this for long enough now to, that most
people agree that there's no polynomial time algorithm for SAT. To start
classifying problems, what we're going to do is kind of adopt that as an assumption.
Or at least we'll classify problems according to the difficulty of, of SAT.
And what that means is we're going to use reduction from SAT. So if we reduce SAT to
some problem. as we talked about in the reduction layer, lecture. That means if we
could solve this problem efficiently, we also could solve that efficiently. And
we're going to, call, a problem like that intractable. if we could solve it
efficiently we could solve SAD efficiently. We don't think we can solve
SAD efficiently. that problem's intractable. So that's, that's our meaning
of the word intractable. Alright, so now what are we gonna do to classify problems?
So, the first thing is which search problems in, in P, so there's no really
easy answer for that except for, devising algorithms. but we do have this reduction
technique that is gonna help us It's, now we can be a little more general than when
we were actually designing algorithms that we we're gonna use and we can have the
reduction take polynomial amount of time before we're insisting on linear time. And
not only that, we can. Take a polynomial number of calls to the, the one that we're
reducing to. And again all this is about is that if you have a polynomial time
algorithm for y then the reduction gives you a polynomial time algorithm for x. And
we're just try ing to have the most general definition that preserves that
property. and so the consequences that if we have a polynomial time reduction from
SAT to a given problem Y, then we can conclude that Y is well, it's intractable.
By our definition. that is it's as difficult as SAT and we think that there
is no polynomial time algorithm for it. So that's a mean tool that we're going to
start out with to use for classifying problems so let's look at an example.
Actually you can work with simpler versions of, of SAT. You can actually
reduce any SAT problem to just a form where you have a bunch of equations using
literals . so, usually we use and so for example like that. So, given that fact to
find a solution. so, now we have another problem IOP given a system of linear
inequalities find a solution. So, what we want to do is, Characterize sat as an ILP
problem. So, that is, if we had an efficient solution to ILP, it'd give us a
solution to sat. So let's take a look at, this example. so our, whatever SAT problem
we have, we put it in this form. and now, we're gonna introduce a variable, C1. and,
for every, literal in the SAT problem. we're gonna, put C1 greater than or = to,
either the literal, if it's not negated. Or one minus the literal if it is negated.
so in this case, . And so we have C1 greater or = to one - x1. Greater than x
or greater than x3, like that. and then we're going to have a fourth inequality.
that says that it has to be less than or equal to the sum of those three. so what
this construction does is if the equation is satisfied, if there's some way to
satisfy this equation then it's going to be C1 equals to one. so that is, if there
is a way to, make each one of these terms one, say by setting X1 to zero, X2 to one
and X3 to one, then this thing will be, those things all will be true. and then
this one also will be true. And all four of these are true. If and only if, the
equation is satisfied. And we make a little group like that for, all four of
the equations. and then we do a, a similar thing wi th a variable that's true if and
only if, all of the c's are true. So this one's, this variable has got to be less
than all four of these. And the only way that this thing's gonna be one, is if all
the equations are satisfied. So this system, has a solution. if and only if,
there's a SAT solution. And from the solution to the system, you can find the
SAT solution. So that's a reduction from SAT to integer linear programming,
programming. Because of this reduction, we feel that we don't, we're not gonna have a
polynomial time solution to integer linear programming. If we did, we'd have a fast
solution to SAT. so that's, that's an important, piece of knowledge where you
focus on this one hard problem that we know about, and that tells us another
problem, is that, the, the reduction tells us another problem that is at least as
hard. and that by itself is interesting integer linear programming is a very
important computation with lots of applications. but the a, amazing thing
that was shown by Dick Carp in the 70s, is that there are lots and lots of problems
that you can reduce satisfiability to. and actually you. Car produced SAT to the so
called independent set problem then reduce that one to aisle P, but if you do two
reductions it still, it still works. if, I could solve ILP quickly. I could solve
independent set quickly. Then, I could use that to solve SAT quickly. so, if you can
prove any problem on this set, you can reduce any problem on this set. To your
new problem that's like proving that SAT reduces to it. So, if we adopt the idea
that SAT is intractable it means that all of these problems are intractable. These
are lots of important problems that people were looking for solutions and couldn't
find good solutions to, and, what Karp shows in the Travelling Salesman problem
and the Hamilton Path problem which is the like problem. Finding the that's the
problem of finding a path on the graph that visits all the vertices. So what,
what Karp showed is that all of these problems are intractable. They're all as
least as difficult to SAP, as SAP. if we had a efficient polynomial times solution
to any one of them, we'd have a polynomial time solution to SAP. that was Quite a
powerful idea of using polynomial time reduction to classify problems in this
way. In fact, it's such a powerful idea that nowadays there's maybe 6000 papers
per year. with reductions from some problem that has, been shown to reduce
from SAT to some new problem. and these are, important problems in, all fields of
human endeavor. so, for example, the so called protein folding problem. Which, in
biochemistry, where, people are trying to understand what's going on, in, living
organisms. has been reduced from SAT. We'd like to solve that problem. But, and that
would help us understand what's going in, in living organisms. much better. but if
we had a, an efficient solution for, a guaranteed polynomial time solution to
that problem. We'd have a, a, a, guaranteed polynomial time solution to
SAT. and so we don't think so, Or, economics, With, if you just make the
arbitrage problem a little more complicated and a little more realistic.
where, there's, a little cost involved with doing things. it turns out to be,
that, you can't have an efficient solution. Not to that one unless, cause it
would imply an efficient solution to SAP. and many, many other examples. Voting
power and politics. Experimental design and statistics. Thousands and thousands of
papers per year involving reductions from sap. Very, very powerful concept, that the
idea of reducing from sets. Now, we have two ways to classify problems. We can,
find a polynomial time algorithm and then we know problems in P, or we can develop a
polynomial time reduction from set and that'll prove that at least if you believe
that sat is difficult you should believe that'll be difficult to find a solution to
your problem. so that's the first step in classifying problems.