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.